DMOPC '14 Contest 2 P4 - Deforestation - Olympiads Online Judge

DMOPC '14 Contest 2 P4 - Deforestation

Points: 5 (partial)

Time limit: 2.5s

Memory limit: 256M

Authors:

Problem type

The Logging Company has a long line of $N$ ~N~ $(1 \le N \le 1\,000\,000)$ ~(1 \le N \le 1\,000\,000)~ trees numbered from $0$ ~0~ to $N-1$ ~N-1~. Each tree $i$ ~i~ has a mass $m_i$ ~m_i~ $(0 \le m_i \le 2000)$ ~(0 \le m_i \le 2000)~. The Company wants to cut some of the trees, so they hired you to calculate the mass of all the wood they would get from cutting all the trees between positions $a$ ~a~ and $b$ ~b~ inclusive $(0 \le a, b < N)$ ~(0 \le a, b < N)~. In particular, they want you to answer $Q$ ~Q~ $(1 \le Q \le 1\,000\,000)$ ~(1 \le Q \le 1\,000\,000)~ such queries.

Input Specification

First line: $N$ ~N~.
Lines $2$ ~2~ to $N+1$ ~N+1~: line $i+2$ ~i+2~ is the mass of tree $i$ ~i~, $m_i$ ~m_i~.
The line $N+2$ ~N+2~ will contain the integer $Q$ ~Q~, the number of queries the logging company wants answered.
The next $Q$ ~Q~ lines will contain the integers $a$ ~a~ and $b$ ~b~.

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~.

Scoring

For 30% of the points, $N, Q \le 1\,000$ ~N, Q \le 1\,000~.
For 50% of the points, $N, Q \le 10\,000$ ~N, Q \le 10\,000~.
For the rest, $N, Q \le 1\,000\,000$ ~N, Q \le 1\,000\,000~.

Sample Input

Sample Output

15
9
3

Comments

4

cabbagecabbagecabbage commented on Nov. 30, 2019, 10:46 p.m. ← edited →

with Python3 if u tle on the last 2 try using fast input

https://dmoj.ca/tips/#python-in

2

hmy20040204 commented on Sept. 23, 2019, 2:54 a.m.

I got a TLE, not sure how to fix it, can anyone help me, thanx XD

8

Tzak commented on Sept. 23, 2019, 12:13 p.m.

This problem requires prefix sum arrays to handle queries in constant time.

2

hmy20040204 commented on Sept. 25, 2019, 11:11 p.m.

Thanks so much

10

FatalEagle commented on Oct. 10, 2015, 3:50 a.m.

cin/cout might be too slow to pass. Try one of the tips!

-3

Dan13llljws commented on Jan. 12, 2020, 1:45 a.m.

How come when I use fast I/O in my IDE it works but when I submit it TLE

3

UnknownSource commented on Sept. 14, 2019, 5:11 p.m.

You are a saint

-1

Kirito commented on May 14, 2016, 9:13 p.m.

Is this question doable in Turing with the current time limit?

2

Xyene commented on May 14, 2016, 9:23 p.m. ← edited →

The OpenTuring we use includes some benchmarks against Python in its README, which might be of help.

Conclusion

Python is faster than Turing.

17

quantum commented on Nov. 19, 2014, 4:22 a.m.

Give PYPY a try. (Why must I rhyme?)

-4

FatalEagle commented on Nov. 20, 2014, 5:30 p.m. ← edited →

Specifically, if you TLE with CPython, use the PyPy interpreter.