Sum insertion P83997
Please implement an efficient data structure to support just one operation. Let x1, …, xn be the current elements (natural numbers) in the data structure, all different and in increasing order. Given three parameters y, i, and j, you must insert z = (y + ∑i ≤ k ≤ j xk) mod109 into your data structure. Assume that you start with just one element, with value 0.
Input
Input begins consists of several cases. Each case starts with the number of insertions m. Follow m triples y i j. Assume 1 ≤ m ≤ 105, 0 ≤ y < 109, and 1 ≤ i ≤ j ≤ n. The end of input is indicated with a special case with m = 0.
Output
For every operation, if z is a new value, insert z and print I z. Otherwise, do not insert z and print R z. Print a line with 10 dashes at the end of each case.
Input
4 5 1 1 3 1 1 2 1 2 3 2 3 5 0 1 1 999999999 1 1 1 2 2 999999999 1 2 999999999 1 3 0
Output
I 5 I 3 R 5 I 11 ---------- R 0 I 999999999 R 0 I 999999998 I 999999996 ----------
- Author
- Pol Mauri
- Language
- English
- Official solutions
- C++
- User solutions
- C C++