DMOPC '14 Contest 2 P4 - Deforestation

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 5.0s
Memory limit: 256M

Authors:
Problem type

The Logging Company has a long line of N (1 \le N \le 1\,000\,000) trees numbered from 0 to N-1. Each tree i has a mass m_i (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 and b inclusive (0 \le a, b < N). In particular, they want you to answer Q (1 \le Q \le 1\,000\,000) such queries.

Input Specification

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

Output Specification

For each query, print the total mass of the trees at position i such that a \le i \le b.

Scoring

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

Sample Input

5
1
2
3
4
5
3
0 4
1 3
2 2

Sample Output

15
9
3

Comments


  • 0
    TypicalToxic  commented on May 12, 2016, 12:18 p.m.

    An internal error occurred while grading, and the DMOJ administrators have been notified. In the meantime, try resubmitting in a few seconds.


    • 2
      Xyene  commented on May 12, 2016, 2:33 p.m.

      Yes, we all get an email whenever an IE occurs. I've fixed the issue, and the problem is working now.


  • 3
    FatalEagle  commented on Oct. 9, 2015, 11:50 p.m.

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


    • -2
      Kirito  commented on May 14, 2016, 5:13 p.m.

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


      • 2
        Xyene  commented on May 14, 2016, 5: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.


  • 8
    quantum  commented on Nov. 18, 2014, 11:22 p.m.

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


    • -4
      FatalEagle  commented on Nov. 20, 2014, 12:30 p.m.

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