# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
205548 | 2020-02-29T07:45:08 Z | Kastanda | Foehn Phenomena (JOI17_foehn_phenomena) | C++11 | 374 ms | 20736 KB |
// In The Name Of The Queen #include<bits/stdc++.h> #define lc (id << 1) #define rc (lc ^ 1) #define md (l + r >> 1) using namespace std; typedef long long ll; const int N = 200005; int n, q, S, T, A[N]; ll F[N], C[N * 4][2]; inline void Add(int i, int val) { for (i ++; i < N; i += i & - i) F[i] += val; } inline ll Get(int i) { ll rt = 0; for (i ++; i; i -= i & - i) rt += F[i]; return (rt); } void Set(int i, ll a, ll b, int id = 1, int l = 0, int r = n) { if (r - l < 2) { C[id][0] = C[id][1] = 0; C[id][a < b] += abs(a - b); return ; } if (i < md) Set(i, a, b, lc, l, md); else Set(i, a, b, rc, md, r); C[id][0] = C[lc][0] + C[rc][0]; C[id][1] = C[lc][1] + C[rc][1]; } int main() { scanf("%d%d%d%d", &n, &q, &S, &T); for (int i = 0; i <= n; i ++) scanf("%d", &A[i]), Add(i, A[i]), Add(i + 1, -A[i]); for (int i = 0; i < n; i ++) Set(i, A[i], A[i + 1]); for (int i = 1; i <= q; i ++) { int l, r, X; scanf("%d%d%d", &l, &r, &X); Add(l, X); Add(r + 1, -X); Set(l - 1, Get(l - 1), Get(l)); if (r < n) Set(r, Get(r), Get(r + 1)); printf("%lld\n", C[1][0] * T - C[1][1] * S); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 504 KB | Output is correct |
2 | Correct | 8 ms | 504 KB | Output is correct |
3 | Correct | 8 ms | 504 KB | Output is correct |
4 | Correct | 7 ms | 504 KB | Output is correct |
5 | Correct | 7 ms | 504 KB | Output is correct |
6 | Correct | 8 ms | 504 KB | Output is correct |
7 | Correct | 9 ms | 504 KB | Output is correct |
8 | Correct | 7 ms | 504 KB | Output is correct |
9 | Correct | 7 ms | 504 KB | Output is correct |
10 | Correct | 8 ms | 504 KB | Output is correct |
11 | Correct | 7 ms | 504 KB | Output is correct |
12 | Correct | 7 ms | 504 KB | Output is correct |
13 | Correct | 7 ms | 504 KB | Output is correct |
14 | Correct | 7 ms | 632 KB | Output is correct |
15 | Correct | 7 ms | 504 KB | Output is correct |
16 | Correct | 7 ms | 504 KB | Output is correct |
17 | Correct | 7 ms | 508 KB | Output is correct |
18 | Correct | 7 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 376 KB | Output is correct |
20 | Correct | 5 ms | 376 KB | Output is correct |
21 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 359 ms | 17668 KB | Output is correct |
2 | Correct | 342 ms | 18544 KB | Output is correct |
3 | Correct | 374 ms | 18892 KB | Output is correct |
4 | Correct | 338 ms | 18416 KB | Output is correct |
5 | Correct | 337 ms | 19424 KB | Output is correct |
6 | Correct | 200 ms | 18476 KB | Output is correct |
7 | Correct | 200 ms | 18552 KB | Output is correct |
8 | Correct | 323 ms | 19452 KB | Output is correct |
9 | Correct | 312 ms | 19576 KB | Output is correct |
10 | Correct | 314 ms | 18296 KB | Output is correct |
11 | Correct | 211 ms | 18524 KB | Output is correct |
12 | Correct | 188 ms | 19192 KB | Output is correct |
13 | Correct | 200 ms | 19448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 504 KB | Output is correct |
2 | Correct | 8 ms | 504 KB | Output is correct |
3 | Correct | 8 ms | 504 KB | Output is correct |
4 | Correct | 7 ms | 504 KB | Output is correct |
5 | Correct | 7 ms | 504 KB | Output is correct |
6 | Correct | 8 ms | 504 KB | Output is correct |
7 | Correct | 9 ms | 504 KB | Output is correct |
8 | Correct | 7 ms | 504 KB | Output is correct |
9 | Correct | 7 ms | 504 KB | Output is correct |
10 | Correct | 8 ms | 504 KB | Output is correct |
11 | Correct | 7 ms | 504 KB | Output is correct |
12 | Correct | 7 ms | 504 KB | Output is correct |
13 | Correct | 7 ms | 504 KB | Output is correct |
14 | Correct | 7 ms | 632 KB | Output is correct |
15 | Correct | 7 ms | 504 KB | Output is correct |
16 | Correct | 7 ms | 504 KB | Output is correct |
17 | Correct | 7 ms | 508 KB | Output is correct |
18 | Correct | 7 ms | 504 KB | Output is correct |
19 | Correct | 5 ms | 376 KB | Output is correct |
20 | Correct | 5 ms | 376 KB | Output is correct |
21 | Correct | 5 ms | 376 KB | Output is correct |
22 | Correct | 359 ms | 17668 KB | Output is correct |
23 | Correct | 342 ms | 18544 KB | Output is correct |
24 | Correct | 374 ms | 18892 KB | Output is correct |
25 | Correct | 338 ms | 18416 KB | Output is correct |
26 | Correct | 337 ms | 19424 KB | Output is correct |
27 | Correct | 200 ms | 18476 KB | Output is correct |
28 | Correct | 200 ms | 18552 KB | Output is correct |
29 | Correct | 323 ms | 19452 KB | Output is correct |
30 | Correct | 312 ms | 19576 KB | Output is correct |
31 | Correct | 314 ms | 18296 KB | Output is correct |
32 | Correct | 211 ms | 18524 KB | Output is correct |
33 | Correct | 188 ms | 19192 KB | Output is correct |
34 | Correct | 200 ms | 19448 KB | Output is correct |
35 | Correct | 346 ms | 18016 KB | Output is correct |
36 | Correct | 355 ms | 19320 KB | Output is correct |
37 | Correct | 369 ms | 20276 KB | Output is correct |
38 | Correct | 357 ms | 19944 KB | Output is correct |
39 | Correct | 360 ms | 19896 KB | Output is correct |
40 | Correct | 351 ms | 20116 KB | Output is correct |
41 | Correct | 362 ms | 19832 KB | Output is correct |
42 | Correct | 362 ms | 19952 KB | Output is correct |
43 | Correct | 348 ms | 19192 KB | Output is correct |
44 | Correct | 370 ms | 19448 KB | Output is correct |
45 | Correct | 340 ms | 19576 KB | Output is correct |
46 | Correct | 346 ms | 20736 KB | Output is correct |
47 | Correct | 205 ms | 19192 KB | Output is correct |
48 | Correct | 231 ms | 19196 KB | Output is correct |
49 | Correct | 320 ms | 18296 KB | Output is correct |
50 | Correct | 209 ms | 18936 KB | Output is correct |
51 | Correct | 197 ms | 19320 KB | Output is correct |
52 | Correct | 229 ms | 19192 KB | Output is correct |