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 ```