#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#else
#define er(args ...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 2e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
ll n, s, t;
ll cr, fen[maxn], a[maxn];
void upd(int i, ll k){
for(i++; i < maxn; i += i&-i) fen[i] += k;
}
ll get(int i){
ll res = 0;
for(i++; i; i -= i&-i) res += fen[i];
return res;
}
ll vl(int i){
if(i - n){
ll x = a[i] + get(i), y = a[i+1] + get(i+1);
return (x - y)*(x < y? s: t);
}
return 0;
}
void upd(int l, int r, int k){
cr -= vl(l-1) + vl(r);
upd(l, k), upd(r+1, -k);
cr += vl(l-1) + vl(r);
}
int main(){ IOS();
int q; cin >> n >> q >> s >> t;
rep(i,0,n+1) cin >> a[i];
rep(i,0,n) cr += vl(i);
while(q--){
int l, r, k; cin >> l >> r >> k;
upd(l, r, k);
cout << cr << '\n';
}
return 0-0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
476 KB |
Output is correct |
7 |
Correct |
2 ms |
476 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
400 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
380 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
121 ms |
5452 KB |
Output is correct |
2 |
Correct |
124 ms |
6132 KB |
Output is correct |
3 |
Correct |
126 ms |
6708 KB |
Output is correct |
4 |
Correct |
120 ms |
5992 KB |
Output is correct |
5 |
Correct |
120 ms |
6592 KB |
Output is correct |
6 |
Correct |
84 ms |
5464 KB |
Output is correct |
7 |
Correct |
85 ms |
5404 KB |
Output is correct |
8 |
Correct |
111 ms |
6976 KB |
Output is correct |
9 |
Correct |
115 ms |
7244 KB |
Output is correct |
10 |
Correct |
119 ms |
5964 KB |
Output is correct |
11 |
Correct |
89 ms |
5496 KB |
Output is correct |
12 |
Correct |
84 ms |
5880 KB |
Output is correct |
13 |
Correct |
85 ms |
6328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
476 KB |
Output is correct |
7 |
Correct |
2 ms |
476 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
400 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
344 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
380 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
121 ms |
5452 KB |
Output is correct |
23 |
Correct |
124 ms |
6132 KB |
Output is correct |
24 |
Correct |
126 ms |
6708 KB |
Output is correct |
25 |
Correct |
120 ms |
5992 KB |
Output is correct |
26 |
Correct |
120 ms |
6592 KB |
Output is correct |
27 |
Correct |
84 ms |
5464 KB |
Output is correct |
28 |
Correct |
85 ms |
5404 KB |
Output is correct |
29 |
Correct |
111 ms |
6976 KB |
Output is correct |
30 |
Correct |
115 ms |
7244 KB |
Output is correct |
31 |
Correct |
119 ms |
5964 KB |
Output is correct |
32 |
Correct |
89 ms |
5496 KB |
Output is correct |
33 |
Correct |
84 ms |
5880 KB |
Output is correct |
34 |
Correct |
85 ms |
6328 KB |
Output is correct |
35 |
Correct |
121 ms |
5640 KB |
Output is correct |
36 |
Correct |
119 ms |
7060 KB |
Output is correct |
37 |
Correct |
120 ms |
7864 KB |
Output is correct |
38 |
Correct |
121 ms |
7584 KB |
Output is correct |
39 |
Correct |
123 ms |
7656 KB |
Output is correct |
40 |
Correct |
123 ms |
7608 KB |
Output is correct |
41 |
Correct |
123 ms |
7440 KB |
Output is correct |
42 |
Correct |
126 ms |
7548 KB |
Output is correct |
43 |
Correct |
120 ms |
6788 KB |
Output is correct |
44 |
Correct |
121 ms |
7304 KB |
Output is correct |
45 |
Correct |
129 ms |
7004 KB |
Output is correct |
46 |
Correct |
139 ms |
7756 KB |
Output is correct |
47 |
Correct |
87 ms |
6052 KB |
Output is correct |
48 |
Correct |
95 ms |
6288 KB |
Output is correct |
49 |
Correct |
112 ms |
6860 KB |
Output is correct |
50 |
Correct |
92 ms |
6080 KB |
Output is correct |
51 |
Correct |
87 ms |
6128 KB |
Output is correct |
52 |
Correct |
94 ms |
6112 KB |
Output is correct |