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 \le N \le 5 \cdot 10^4~

$1 \le Q \le 2 \cdot 10^5$ ~1 \le Q \le 2 \cdot 10^5~

$1 \le a_i \le b_i \le N$ ~1 \le a_i \le b_i \le N~

$a_i, b_i \in \mathbb{C}$ ~a_i, b_i \in \mathbb{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

Sample Output

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.