# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
112306 | 2019-05-18T16:15:28 Z | Mercenary | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 163 ms | 13176 KB |
#include<bits/stdc++.h> using namespace std; #define taskname "A" #define pb push_back #define mp make_pair #ifndef LOCAL #define cerr if(0)cout #endif typedef long double ld; typedef long long ll; typedef pair<int,int> ii; const int maxn = 2e5 + 5; int s , t , n , q; ll a[maxn] , b[maxn]; void update(int x , int delta){ for( ; x <= n ; x += x & -x) a[x] += delta; } ll query(int x){ ll res = 0; for( ; x > 0 ; x &= x - 1) res += a[x]; return res; } ll get(ll pre , ll now , ll add){ ll res = 0; if(pre <= now){ res += (ll)s * (now - pre); }else res -= (ll)t * (pre - now); now += add; if(pre <= now){ res -= (ll)s * (now - pre); }else res += (ll)t * (pre - now); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } cin >> n >> q >> s >> t; ll res = 0; for(int i = 0 ; i <= n ; ++i){ cin >> b[i]; if(i > 0){ update(i,b[i]-b[i - 1]); if(b[i] >= b[i - 1]){ res -= s * (ll)(b[i] - b[i - 1]); // cout << i << " "; }else{ res += t * (ll)(b[i - 1] - b[i]); } } // cout << res << endl; } for(int i = 1 ; i <= q ; ++i){ int x , y , val;cin >> x >> y >> val; res += get(query(x - 1) , query(x) , val); if(y != n)res += get(query(y) , query(y + 1) , -val); update(x,val); update(y + 1 , -val); cout << res << '\n'; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 512 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 4 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 572 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
15 | Correct | 3 ms | 512 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 3 ms | 512 KB | Output is correct |
18 | Correct | 3 ms | 512 KB | Output is correct |
19 | Correct | 2 ms | 392 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 2 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 132 ms | 10264 KB | Output is correct |
2 | Correct | 134 ms | 10876 KB | Output is correct |
3 | Correct | 145 ms | 11536 KB | Output is correct |
4 | Correct | 148 ms | 10872 KB | Output is correct |
5 | Correct | 162 ms | 12024 KB | Output is correct |
6 | Correct | 110 ms | 11128 KB | Output is correct |
7 | Correct | 120 ms | 11048 KB | Output is correct |
8 | Correct | 144 ms | 11768 KB | Output is correct |
9 | Correct | 151 ms | 12172 KB | Output is correct |
10 | Correct | 140 ms | 11000 KB | Output is correct |
11 | Correct | 111 ms | 11000 KB | Output is correct |
12 | Correct | 111 ms | 11640 KB | Output is correct |
13 | Correct | 110 ms | 11816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 512 KB | Output is correct |
2 | Correct | 3 ms | 512 KB | Output is correct |
3 | Correct | 3 ms | 512 KB | Output is correct |
4 | Correct | 3 ms | 512 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 3 ms | 512 KB | Output is correct |
10 | Correct | 4 ms | 512 KB | Output is correct |
11 | Correct | 3 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 572 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
15 | Correct | 3 ms | 512 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 3 ms | 512 KB | Output is correct |
18 | Correct | 3 ms | 512 KB | Output is correct |
19 | Correct | 2 ms | 392 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 2 ms | 384 KB | Output is correct |
22 | Correct | 132 ms | 10264 KB | Output is correct |
23 | Correct | 134 ms | 10876 KB | Output is correct |
24 | Correct | 145 ms | 11536 KB | Output is correct |
25 | Correct | 148 ms | 10872 KB | Output is correct |
26 | Correct | 162 ms | 12024 KB | Output is correct |
27 | Correct | 110 ms | 11128 KB | Output is correct |
28 | Correct | 120 ms | 11048 KB | Output is correct |
29 | Correct | 144 ms | 11768 KB | Output is correct |
30 | Correct | 151 ms | 12172 KB | Output is correct |
31 | Correct | 140 ms | 11000 KB | Output is correct |
32 | Correct | 111 ms | 11000 KB | Output is correct |
33 | Correct | 111 ms | 11640 KB | Output is correct |
34 | Correct | 110 ms | 11816 KB | Output is correct |
35 | Correct | 146 ms | 10488 KB | Output is correct |
36 | Correct | 146 ms | 11820 KB | Output is correct |
37 | Correct | 151 ms | 12664 KB | Output is correct |
38 | Correct | 156 ms | 12504 KB | Output is correct |
39 | Correct | 151 ms | 12408 KB | Output is correct |
40 | Correct | 163 ms | 12536 KB | Output is correct |
41 | Correct | 153 ms | 12280 KB | Output is correct |
42 | Correct | 160 ms | 12408 KB | Output is correct |
43 | Correct | 151 ms | 11640 KB | Output is correct |
44 | Correct | 140 ms | 12176 KB | Output is correct |
45 | Correct | 150 ms | 12152 KB | Output is correct |
46 | Correct | 144 ms | 13176 KB | Output is correct |
47 | Correct | 107 ms | 11644 KB | Output is correct |
48 | Correct | 138 ms | 11664 KB | Output is correct |
49 | Correct | 132 ms | 10744 KB | Output is correct |
50 | Correct | 112 ms | 11512 KB | Output is correct |
51 | Correct | 106 ms | 11896 KB | Output is correct |
52 | Correct | 112 ms | 11636 KB | Output is correct |