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 \le N \le 100\,000)~ trees. Each tree $i$ ~i~ has a mass $m_i$ ~m_i~ $(1 \le m_i \le 20\,000)$ ~(1 \le m_i \le 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 \le q \le 20\,000)~ between positions $a$ ~a~ and $b$ ~b~ inclusive $(0 \le a \le b < N)$ ~(0 \le a \le b < N)~. In particular, they want you to answer $Q$ ~Q~ $(1 \le Q \le 100\,000)$ ~(1 \le Q \le 100\,000)~ such queries.

Input Specification

The first line will contain the integer $N$ ~N~. For each tree $i$ ~i~, the $i^{th}$ ~i^{th}~ (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 \le i \le b~, and $m_i \ge q$ ~m_i \ge q~.

Sample Input

Sample Output

Comments

-10

Xue_Alex commented on July 19, 2017, 9:26 p.m.

weak test data???

i submitted my program and after getting wa'd i realized that there was a very big flaw (check lines 80 and 81 in my 85/100) but i still got a couple batches correct.

This comment is hidden due to too much negative feedback. Show it anyway.

0

pyrexshorts commented on March 28, 2015, 4:14 a.m.

My solution doesn't work for the 3rd batch test case, can anyone give me a hint why?

8

bruce commented on March 28, 2015, 4:03 p.m.

2 mistakes in your code: 1) "ans" in your query structure is int, not long long. It will overflow. 2) x=max(x,q) is not right, since some mass is much larger than the query. Your solution ignores all masses which are bigger than the largest query. So, x in your code should be the largest of all a and all q. Fix these mistakes, you'll AC.

1

pop commented on March 27, 2015, 3:07 a.m.

Can anyone share an algorithm that doesn't involve iterating through all trees from a - b?

4

kobortor commented on March 27, 2015, 3:12 a.m. ← edited →

I would, but if I did fatal would get mad at me for violating TOS and stuff.

Edit: Xyene is nice.

2

pop commented on March 27, 2015, 3:16 a.m.

Ah. sorry. I wasn't aware. I'm more interested in the learning aspect than the points system. I've see what you mean in the TOS.

4

FatalEagle commented on March 27, 2015, 3:17 a.m. ← edit 2 →

Learning is fine. However, the comments section is not the appropriate place to discuss this topic -- we have editorials for this particular problem at https://dmoj.ca/problem/dmopc14c2p6/editorial.

1

pop commented on March 27, 2015, 3:18 a.m.

I see, thanks.