codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.