# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158027 | 2019-10-14T13:04:15 Z | ZwariowanyMarcin | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 301 ms | 12336 KB |
#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define mp make_pair #define pb push_back #define ld long double #define ss(x) (int) x.size() #define FOR(i, j, n) for(int i = j; i <= n; ++i) #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl; #define ios cin.tie(0); ios_base::sync_with_stdio(0) using namespace std; int n, q; int a[200000 + 111]; ll res = 0; int s, t; int l, r, x; struct fenwick { ll add[200000 + 111]; void init() { FOR(i, 1, 200000) add[i] = 0; } void dodaj(int x, int c) { for(; x <= 200000; x += x & -x) add[x] += c; } ll daj(int x) { ll res = 0; for(; 0 < x; x -= x & -x) res += add[x]; return res; } ll sum(int id) { return daj(200000) - daj(id - 1); } } ja; void roll(int x) { if(x <= 1 || x > n + 1) return; ll k = abs(ja.sum(x) - ja.sum(x - 1)); if(ja.sum(x) > ja.sum(x - 1)) res += (ll) s * k; else res -= (ll) t * k; } void akt(int x) { if(x <= 1 || x > n + 1) return; ll k = abs(ja.sum(x) - ja.sum(x - 1)); if(ja.sum(x) > ja.sum(x - 1)) res -= (ll) s * k; else res += (ll) t * k; } int main() { ja.init(); scanf("%d %d %d %d", &n, &q, &s, &t); FOR(i, 1, n + 1) scanf("%d", &a[i]); FOR(i, 2, n + 1) { ja.dodaj(i, a[i]); ja.dodaj(i - 1, -a[i]); } FOR(i, 2, n + 1) akt(i); FOR(i, 1, q) { scanf("%d %d %d", &l, &r, &x); l += 1; r += 1; roll(l); roll(r + 1); ja.dodaj(r, x); ja.dodaj(l - 1, -x); akt(l); akt(r + 1); printf("%lld\n", res); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1912 KB | Output is correct |
2 | Correct | 6 ms | 2040 KB | Output is correct |
3 | Correct | 6 ms | 2040 KB | Output is correct |
4 | Correct | 6 ms | 2044 KB | Output is correct |
5 | Correct | 6 ms | 2040 KB | Output is correct |
6 | Correct | 5 ms | 1912 KB | Output is correct |
7 | Correct | 6 ms | 1912 KB | Output is correct |
8 | Correct | 6 ms | 1916 KB | Output is correct |
9 | Correct | 6 ms | 2040 KB | Output is correct |
10 | Correct | 5 ms | 2040 KB | Output is correct |
11 | Correct | 5 ms | 1912 KB | Output is correct |
12 | Correct | 5 ms | 1912 KB | Output is correct |
13 | Correct | 5 ms | 1912 KB | Output is correct |
14 | Correct | 5 ms | 1912 KB | Output is correct |
15 | Correct | 5 ms | 1912 KB | Output is correct |
16 | Correct | 5 ms | 2040 KB | Output is correct |
17 | Correct | 5 ms | 1912 KB | Output is correct |
18 | Correct | 5 ms | 2040 KB | Output is correct |
19 | Correct | 6 ms | 1912 KB | Output is correct |
20 | Correct | 3 ms | 1912 KB | Output is correct |
21 | Correct | 3 ms | 1912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 264 ms | 4772 KB | Output is correct |
2 | Correct | 270 ms | 5472 KB | Output is correct |
3 | Correct | 270 ms | 6100 KB | Output is correct |
4 | Correct | 249 ms | 5516 KB | Output is correct |
5 | Correct | 250 ms | 6140 KB | Output is correct |
6 | Correct | 176 ms | 6520 KB | Output is correct |
7 | Correct | 178 ms | 6620 KB | Output is correct |
8 | Correct | 252 ms | 6644 KB | Output is correct |
9 | Correct | 248 ms | 6884 KB | Output is correct |
10 | Correct | 244 ms | 5704 KB | Output is correct |
11 | Correct | 182 ms | 6752 KB | Output is correct |
12 | Correct | 168 ms | 7208 KB | Output is correct |
13 | Correct | 177 ms | 11256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1912 KB | Output is correct |
2 | Correct | 6 ms | 2040 KB | Output is correct |
3 | Correct | 6 ms | 2040 KB | Output is correct |
4 | Correct | 6 ms | 2044 KB | Output is correct |
5 | Correct | 6 ms | 2040 KB | Output is correct |
6 | Correct | 5 ms | 1912 KB | Output is correct |
7 | Correct | 6 ms | 1912 KB | Output is correct |
8 | Correct | 6 ms | 1916 KB | Output is correct |
9 | Correct | 6 ms | 2040 KB | Output is correct |
10 | Correct | 5 ms | 2040 KB | Output is correct |
11 | Correct | 5 ms | 1912 KB | Output is correct |
12 | Correct | 5 ms | 1912 KB | Output is correct |
13 | Correct | 5 ms | 1912 KB | Output is correct |
14 | Correct | 5 ms | 1912 KB | Output is correct |
15 | Correct | 5 ms | 1912 KB | Output is correct |
16 | Correct | 5 ms | 2040 KB | Output is correct |
17 | Correct | 5 ms | 1912 KB | Output is correct |
18 | Correct | 5 ms | 2040 KB | Output is correct |
19 | Correct | 6 ms | 1912 KB | Output is correct |
20 | Correct | 3 ms | 1912 KB | Output is correct |
21 | Correct | 3 ms | 1912 KB | Output is correct |
22 | Correct | 264 ms | 4772 KB | Output is correct |
23 | Correct | 270 ms | 5472 KB | Output is correct |
24 | Correct | 270 ms | 6100 KB | Output is correct |
25 | Correct | 249 ms | 5516 KB | Output is correct |
26 | Correct | 250 ms | 6140 KB | Output is correct |
27 | Correct | 176 ms | 6520 KB | Output is correct |
28 | Correct | 178 ms | 6620 KB | Output is correct |
29 | Correct | 252 ms | 6644 KB | Output is correct |
30 | Correct | 248 ms | 6884 KB | Output is correct |
31 | Correct | 244 ms | 5704 KB | Output is correct |
32 | Correct | 182 ms | 6752 KB | Output is correct |
33 | Correct | 168 ms | 7208 KB | Output is correct |
34 | Correct | 177 ms | 11256 KB | Output is correct |
35 | Correct | 279 ms | 9744 KB | Output is correct |
36 | Correct | 281 ms | 11140 KB | Output is correct |
37 | Correct | 284 ms | 11836 KB | Output is correct |
38 | Correct | 272 ms | 11640 KB | Output is correct |
39 | Correct | 275 ms | 11640 KB | Output is correct |
40 | Correct | 276 ms | 11624 KB | Output is correct |
41 | Correct | 277 ms | 11536 KB | Output is correct |
42 | Correct | 301 ms | 11728 KB | Output is correct |
43 | Correct | 273 ms | 10844 KB | Output is correct |
44 | Correct | 286 ms | 11344 KB | Output is correct |
45 | Correct | 261 ms | 11512 KB | Output is correct |
46 | Correct | 260 ms | 12336 KB | Output is correct |
47 | Correct | 182 ms | 10968 KB | Output is correct |
48 | Correct | 214 ms | 10888 KB | Output is correct |
49 | Correct | 255 ms | 9976 KB | Output is correct |
50 | Correct | 187 ms | 10776 KB | Output is correct |
51 | Correct | 172 ms | 11128 KB | Output is correct |
52 | Correct | 198 ms | 10868 KB | Output is correct |