Submit | All submissions | Best solutions | Back to list |
RRANGE - Ranges |
There are N contiguous cells numbered from 1 to N. Initially, each cell contains a 0 in it. A sub-contiguous group of cells can be updated this way:
- A range [i, j] is defined such that i < j
- The cell numbered i is added 1; the cell numbered i + 1 is added 2, and so on until the cell numbered j is reached and added j – i + 1
For example, if N = 7 and the updates [3, 6] and [4, 7] were performed, this is what would happen.
- Initially: {0, 0, 0, 0, 0, 0, 0}
- Update [3, 6]: {0, 0, 1, 2, 3, 4, 0}
- Update [4, 7]: {0, 0, 1, 3, 5, 7, 4}
After performing some update operations, it would be amazing to answer questions like the following:
- A range [u, v] is defined such that u < v.
- The answer is the sum of every cell in the range [u, v] (both u and v are included) modulus 10,000.
Given N and U updates ranges. You have to write a program capable of answering Q questions.
Input
The first line contains three integers: N (1 ≤ N ≤ 1, 000,000,000), U and Q (1 ≤ U, Q ≤ 1, 000), representing the number of cells, the number of update operations, and the number of questions respectively.
Each of the following U lines contains two integers i and j (1 ≤ i < j ≤ N) separated by a single space indicating an update operation.
Each of the following Q lines contains two integers u and v (1 ≤ u < v ≤ N) separated by a single space indicating a question.
Output
For each question [u, v] you must print the sum of all contiguous cells starting at u and ending at v modulus 10,000.
Example
Input: 7 2 2 3 6 4 7 4 6 1 7 Output: 15 20
Added by: | Angel Paredes |
Date: | 2012-02-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Copa Lenin 2012 - Level 1 |
hide comments
2014-06-15 09:58:28 fanatique
can't we solve using BIT? |
|
2014-06-14 17:41:33 aristofanis
@npsabari: It can be solved with segment tree with complexity O((U+Q) log N), although the implementation will be very tricky... Notice that one should perform some kind of space reduction in order to get AC. Last edit: 2014-06-14 17:42:09 |
|
2014-01-28 10:14:43 npsabari
Did anyone manage to solve it in complexity better than O(U*Q)? |
|
2013-12-17 21:39:44 rahul kumar
nice problem...:P |
|
2013-01-18 06:57:28 Vikas Kushwaha
Such a nice question.. enjoyed solving it... |
|
2012-12-25 09:48:13 Ehor Nechiporenko
So NICE!! |
|
2012-07-05 10:54:14 DaRksTar
weird !! |
|
2012-07-05 07:14:46 Romal Thoppilan
Tough time debugging .. ! |
|
2012-02-20 03:58:40 Angel Paredes
Both updates and questions are defined by two integers between 1 and N, so the test case you are asking for is incorrect. There are no tricky test cases. Everything should go fine with the proper solution. Last edit: 2012-02-20 04:02:09 |