Mock CCO '18 Contest 3 Problem 4 - Roger Solves A Classic Rage Tree Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 0.3s

Java 0.6s

Memory limit: 64M

Problem type

Roger is training for CCO and has decided to practice implementing rage trees. He decides to solve a classic problem that is solvable with rage trees.

Given an array with $N$ $N$ integers and $Q$ $Q$ subarray queries, compute the range of each subarray.

Constraints

$1 \le N \le 5 \cdot 10^4$ $1 \leq N \leq 5 \cdot 10^{4}$

$1 \le Q \le 2 \cdot 10^5$ $1 \leq Q \leq 2 \cdot 10^{5}$

$1 \le a_i \le b_i \le N$ $1 \leq a_{i} \leq b_{i} \leq N$

$a_i, b_i \in \mathbb{C}$ $a_{i}, b_{i} \in C$

The elements of the array are positive integers up to a million.

Input Specification

The first line contains two integers, $N$ $N$ and $Q$ $Q$ .

Each of the next $N$ $N$ lines contains a single integer. These $N$ $N$ lines constitute the values of the array in order.

Each of the next $Q$ $Q$ lines contains two integers, $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , indicating a 1-indexed query.

Output Specification

For each query, print on a separate line the range of the subarray with leftmost index $a_i$ $a_{i}$ and rightmost index $b_i$ $b_{i}$ .

Sample Input

Copy

Sample Output

Copy

6
3
0

Comments

0

can definitely solve contest problems in 4 seconds commented on Sept. 17, 2023, 2:58 p.m.

why am i getting presentation error: https://dmoj.ca/submission/5779275

1

Xyene commented on Sept. 17, 2023, 7:59 p.m.

The output of your submission does not match the output format of the problem. If you tried the sample case locally, you'd see why.

0

can definitely solve contest problems in 4 seconds commented on Sept. 17, 2023, 8:55 p.m.

but i have tried it in an editor and the sample case works fine

1

dnialh_ commented on Sept. 19, 2023, 6:04 a.m.

If your editor is somehow displaying output incorrectly you can also see the output of your program on the first testcase in DMOJ by clicking on the arrow on the left.