57B.md (3070B)
1 Source: https://codeforces.com/problemset/problem/57/B 2 3 B. Martian Architecture 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 stdin 16 17 output 18 19 stdout 20 21 Chris the Rabbit found the traces of an ancient Martian civilization. The brave astronomer managed to see through a small telescope an architecture masterpiece — "A Road to the Sun". The building stands on cubical stones of the same size. The foundation divides the entire "road" into cells, into which the cubical stones are fit tightly. Thus, to any cell of the foundation a coordinate can be assigned. To become the leader of the tribe, a Martian should build a Road to the Sun, that is to build from those cubical stones on a given foundation a stairway. The stairway should be described by the number of stones in the initial coordinate and the coordinates of the stairway's beginning and end. Each following cell in the coordinate's increasing order should contain one cubical stone more than the previous one. At that if the cell has already got stones, they do not count in this building process, the stairways were simply built on them. In other words, let us assume that a stairway is built with the initial coordinate of *l*, the final coordinate of *r* and the number of stones in the initial coordinate *x*. That means that *x* stones will be added in the cell *l*, *x* + 1 stones will be added in the cell *l* + 1, ..., *x* + *r* - *l* stones will be added in the cell *r*. 22 23 Chris managed to find an ancient manuscript, containing the descriptions of all the stairways. Now he wants to compare the data to be sure that he has really found "A Road to the Sun". For that he chose some road cells and counted the total number of cubical stones that has been accumulated throughout the Martian history and then asked you to count using the manuscript to what the sum should ideally total. 24 25 Input 26 27 The first line contains three space-separated integers: *n*, *m*, *k* (1 ≤ *n*, *m* ≤ 105, 1 ≤ *k* ≤ *min*(*n*, 100)) which is the number of cells, the number of "Roads to the Sun" and the number of cells in the query correspondingly. Each of the following *m* roads contain three space-separated integers: *a**i*, *b**i*, *c**i* (1 ≤ *a**i* ≤ *b**i* ≤ *n*, 1 ≤ *c**i* ≤ 1000) which are the stairway's description, its beginning, end and the initial cell's height. Then follow a line, containing *k* different space-separated integers *b**i*. All these numbers ranging from 1 to *n* are cells, the number of stones in which interests Chris. 28 29 Output 30 31 You have to print a single number on a single line which is the sum of stones in all the cells Chris is interested in. 32 33 Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d). 34 35 Examples 36 37 Input 38 39 ``` 40 5 2 1 41 1 5 1 42 2 4 1 43 3 44 ``` 45 46 Output 47 48 ``` 49 5 50 ``` 51 52 Input 53 54 ``` 55 3 2 1 56 1 3 1 57 1 3 1 58 2 59 ``` 60 61 Output 62 63 ``` 64 4 65 ``` 66 67 Input 68 69 ``` 70 3 2 1 71 1 3 1 72 1 3 1 73 3 74 ``` 75 76 Output 77 78 ``` 79 6 80 ```