835C.md (2666B)
1 Source: https://codeforces.com/problemset/problem/835/C 2 3 C. Star sky 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The Cartesian coordinate system is set in the sky. There you can see *n* stars, the *i*-th has coordinates (*x**i*, *y**i*), a maximum brightness *c*, equal for all stars, and an initial brightness *s**i* (0 ≤ *s**i* ≤ *c*). 22 23 Over time the stars twinkle. At moment 0 the *i*-th star has brightness *s**i*. Let at moment *t* some star has brightness *x*. Then at moment (*t* + 1) this star will have brightness *x* + 1, if *x* + 1 ≤ *c*, and 0, otherwise. 24 25 You want to look at the sky *q* times. In the *i*-th time you will look at the moment *t**i* and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (*x*1*i*, *y*1*i*) and the upper right — (*x*2*i*, *y*2*i*). For each view, you want to know the total brightness of the stars lying in the viewed rectangle. 26 27 A star lies in a rectangle if it lies on its border or lies strictly inside it. 28 29 Input 30 31 The first line contains three integers *n*, *q*, *c* (1 ≤ *n*, *q* ≤ 105, 1 ≤ *c* ≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars. 32 33 The next *n* lines contain the stars description. The *i*-th from these lines contains three integers *x**i*, *y**i*, *s**i* (1 ≤ *x**i*, *y**i* ≤ 100, 0 ≤ *s**i* ≤ *c* ≤ 10) — the coordinates of *i*-th star and its initial brightness. 34 35 The next *q* lines contain the views description. The *i*-th from these lines contains five integers *t**i*, *x*1*i*, *y*1*i*, *x*2*i*, *y*2*i* (0 ≤ *t**i* ≤ 109, 1 ≤ *x*1*i* < *x*2*i* ≤ 100, 1 ≤ *y*1*i* < *y*2*i* ≤ 100) — the moment of the *i*-th view and the coordinates of the viewed rectangle. 36 37 Output 38 39 For each view print the total brightness of the viewed stars. 40 41 Examples 42 43 Input 44 45 ``` 46 2 3 3 47 1 1 1 48 3 2 0 49 2 1 1 2 2 50 0 2 1 4 5 51 5 1 1 5 5 52 ``` 53 54 Output 55 56 ``` 57 3 58 0 59 3 60 ``` 61 62 Input 63 64 ``` 65 3 4 5 66 1 1 2 67 2 3 0 68 3 3 1 69 0 1 1 100 100 70 1 2 2 4 4 71 2 2 1 4 7 72 1 50 50 51 51 73 ``` 74 75 Output 76 77 ``` 78 3 79 3 80 5 81 0 82 ``` 83 84 Note 85 86 Let's consider the first example. 87 88 At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3. 89 90 At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0. 91 92 At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.