DMOPC '14 Contest 2 P6 - Selective Cutting - Olympiads Online Judge

DMOPC '14 Contest 2 P6 - Selective Cutting

Points: 12 (partial)

Time limit: 0.25s

Java 1.0s

Python 1.0s

Memory limit: 128M

Authors:

quantum, Xyene, FatalEagle

Problem type

The Logging Company has been hit with a petition from concerned citizens regarding their uncontrolled tree-cutting. For public relations purposes, they have decided that, moving forward, they will only cut down trees with mass above a certain threshold.

The Logging Company has a line of $N$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ trees. Each tree $i$ $i$ has a mass $m_i$ $m_{i}$ $(1 \le m_i \le 20\,000)$ $(1 \leq m_{i} \leq 20 000)$ . The Company wants to cut some of the trees, so they've hired you to calculate the mass of all the wood they would get from cutting all the trees with $m_i$ $m_{i}$ greater than or equal to $q$ $q$ $(1 \le q \le 20\,000)$ $(1 \leq q \leq 20 000)$ between positions $a$ $a$ and $b$ $b$ inclusive $(0 \le a \le b < N)$ $(0 \leq a \leq b < N)$ . In particular, they want you to answer $Q$ $Q$ $(1 \le Q \le 100\,000)$ $(1 \leq Q \leq 100 000)$ such queries.

Input Specification

The first line will contain the integer $N$ $N$ . For each tree $i$ $i$ , the $i^{th}$ $i^{t h}$ (from 0) integer on the second line will contain the integer mass $m_i$ $m_{i}$ . The third line will contain the number $Q$ $Q$ , the number of queries the logging company wants you to answer. The next $Q$ $Q$ lines will contain three integers $a$ $a$ and $b$ $b$ and $q$ $q$ .

Output Specification

For each query, print the total mass of the trees at position $i$ $i$ such that $a \le i \le b$ $a \leq i \leq b$ , and $m_i \ge q$ $m_{i} \geq q$ .

Sample Input

Copy

Sample Output

Copy

Comments

1

erniethatrandomguy12 commented on July 26, 2023, 12:16 a.m.

Is there somewhere you can find test cases for DMOPC problems?

4

Kirito commented on July 26, 2023, 1:48 a.m.

You should learn how to come up with testcases on your own -- after all, most contests won't be nice enough to give you access to their test cases.

1

erniethatrandomguy12 commented on July 26, 2023, 1:51 p.m.

ok, thanks