시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 78 | 47 | 30 | 57.692% |
There are N districts in JOI Village, numbered from 1 to N. These districts are located in a line. Now, a fire occurs in each district. At time 0, the strength of the fire in the i-th district (1 ≤ i ≤ N) is Si (Si > 0).
At time 0, the wind blows from the 1st district to the N-th district. For every pair of neighboring districts, if the fire in the upwind district is stronger than the fire in the downwind district at time t (0 ≤ t), the strength of the fire in the downwind district at time t +1 will be the strength of the fire in the upwind district at time t. Otherwise, the strength of the fire in the downwind district at time t +1 and time t are the same. Namely, if the strength of the fire in the i-th district (1 ≤ i ≤ N) at time t (0 ≤ t) is denoted by Si(t), we have Si(t) = max{Si−1(t − 1), Si(t − 1)} for every t (1 ≤ t). Here, for any t (0 ≤ t), we put S0(t) = 0. For any i (1 ≤ i ≤ N), we put Si(0) = Si.
You are a firefighter. You have Q plans to extinguish the fire. You are planning to do only one of the Q plans. In the j-th plan (1 ≤ j ≤ Q), you will use fire extinguishing agent for the k-th district for every k with Lj ≤ k ≤ Rj, and extinguish the fire in these districts. If the strength of the fire in a district is s, you need s liters of fire extinguishing agent to extinguish the fire in that district. Therefore, the amount of fire extinguishing agent needed for the j-th plan is SLj(Tj) + SLj+1(Tj) + · · · + SRj (Tj) liters. In order to examine the plan to be done, you want to know the amount of fire extinguishing agent needed for each plan.
Write a program which, given the strength of the fire at time 0 and information of fire extinguishing plans, calculates the amount of fire extinguishing agent needed for each plan.
Read the following data from the standard input. Given values are all integers.
N Q S1 . . . SN T1 L1 R1 . . . TQ LQ RQ
Write Q lines to the standard output. In the j-th line (1 ≤ j ≤ Q), output the amount of fire extinguishing agent needed for the j-th plan.
번호 | 배점 | 제한 |
---|---|---|
1 | 1 | N ≤ 200, Q ≤ 200. |
2 | 6 | T1 = T2 = · · · = TQ. |
3 | 7 | Lj = Rj (1 ≤ j ≤ Q). |
4 | 6 | Si ≤ 2 (1 ≤ i ≤ N). |
5 | 80 | No additional constraints. |
5 5 9 3 2 6 5 1 1 3 2 1 5 3 2 5 4 3 3 5 3 5
21 39 33 9 27
10 10 3 1 4 1 5 9 2 6 5 3 1 1 6 2 8 10 4 2 7 8 3 3 6 1 10 3 2 8 5 1 9 7 4 5 9 7 9 10 10 10
28 21 34 4 64 43 55 9 27 9
10 10 3 1 4 1 5 9 2 6 5 3 1 6 6 2 8 8 4 2 2 8 3 3 6 1 1 3 4 4 5 5 5 7 10 10 9 8 8 10 7 7
9 9 3 4 3 4 5 9 9 9
10 10 3 1 4 1 5 9 2 6 5 3 7 1 6 7 8 10 7 2 7 7 3 3 7 1 10 7 2 8 7 1 9 7 4 5 7 7 9 7 10 10
28 27 34 4 64 43 55 9 27 9
20 20 2 1 2 2 1 1 1 1 2 2 2 1 2 1 1 2 1 2 1 1 1 1 14 2 3 18 4 10 15 8 2 17 9 20 20 4 8 19 7 2 20 11 1 5 13 2 8 20 1 20 2 12 15 7 1 14 12 7 18 14 2 17 9 19 20 12 12 12 6 2 15 11 2 15 19 12 17 4 1 20
25 30 12 32 2 24 38 10 14 40 8 28 24 32 4 2 28 28 12 40