codeforces-scrape

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

295A.md (2075B)


      1 Source: https://codeforces.com/problemset/problem/295/A
      2 
      3 A. Greg and Array
      4 
      5 time limit per test
      6 
      7 1.5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Greg has an array *a* = *a*1, *a*2, ..., *a**n* and *m* operations. Each operation looks as: *l**i*, *r**i*, *d**i*, (1 ≤ *l**i* ≤ *r**i* ≤ *n*). To apply operation *i* to the array means to increase all array elements with numbers *l**i*, *l**i* + 1, ..., *r**i* by value *d**i*.
     22 
     23 Greg wrote down *k* queries on a piece of paper. Each query has the following form: *x**i*, *y**i*, (1 ≤ *x**i* ≤ *y**i* ≤ *m*). That means that one should apply operations with numbers *x**i*, *x**i* + 1, ..., *y**i* to the array.
     24 
     25 Now Greg is wondering, what the array *a* will be after all the queries are executed. Help Greg.
     26 
     27 Input
     28 
     29 The first line contains integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 105). The second line contains *n* integers: *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 105) — the initial array.
     30 
     31 Next *m* lines contain operations, the operation number *i* is written as three integers: *l**i*, *r**i*, *d**i*, (1 ≤ *l**i* ≤ *r**i* ≤ *n*), (0 ≤ *d**i* ≤ 105).
     32 
     33 Next *k* lines contain the queries, the query number *i* is written as two integers: *x**i*, *y**i*, (1 ≤ *x**i* ≤ *y**i* ≤ *m*).
     34 
     35 The numbers in the lines are separated by single spaces.
     36 
     37 Output
     38 
     39 On a single line print *n* integers *a*1, *a*2, ..., *a**n* — the array after executing all the queries. Separate the printed numbers by spaces.
     40 
     41 Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 3 3 3  
     49 1 2 3  
     50 1 2 1  
     51 1 3 2  
     52 2 3 4  
     53 1 2  
     54 1 3  
     55 2 3
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 9 18 17
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 1 1 1  
     68 1  
     69 1 1 1  
     70 1 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 2
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 4 3 6  
     83 1 2 3 4  
     84 1 2 1  
     85 2 3 2  
     86 3 4 4  
     87 1 2  
     88 1 3  
     89 2 3  
     90 1 2  
     91 1 3  
     92 2 3
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 5 18 31 20
     99 ```