#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn=2e5+10;
ll n,m,S,T;
vector<ll> a;
ll t[3*mxn];
bool flag[3*mxn];
void build(int v,int tl,int tr) {
if(tl==tr) t[v]=a[tl];
else {
int mid=(tl+tr)/2;
build(2*v,tl,mid);
build(2*v+1,mid+1,tr);
}
}
void add(int v,int tl,int tr,int l,int r,int val) {
if(tl>tr or tl>r or tr<l) return;
if(tl>=l and tr<=r) t[v]+=val;
else {
int mid=(tl+tr)/2;
add(2*v,tl,mid,l,r,val);
add(2*v+1,mid+1,tr,l,r,val);
}
}
ll get(int v,int tl,int tr,int idx) {
if(tl==tr) return t[v];
int mid=(tl+tr)/2;
if(idx<=mid) return t[v]+get(2*v,tl,mid,idx);
else return t[v]+get(2*v+1,mid+1,tr,idx);
}
void print() {
for(int i=0;i<n;i++) {
cout<<get(1,0,n-1,i)<<" ";
}
cout<<endl;
}
ll f(ll u,ll v) {
if(u<v) return -1LL*S*(v-u);
return 1LL*T*(u-v);
}
int main () {
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>S>>T; n++;
a.resize(n);
for(int i=0;i<n;i++) cin>>a[i];
build(1,0,n-1);
ll ans=0;
for(int i=1;i<n;i++) {
ans+=f(a[i-1],a[i]);
}
// debug(ans);
for(int i=0;i<m;i++) {
ll l,r,x; cin>>l>>r>>x;
if(l-1>=0) {
ll a1=get(1,0,n-1,l-1);
ll a2=get(1,0,n-1,l);
// debug(a1,a2,f(a1,a2));
ans-=f(a1,a2);
ans+=f(a1,a2+x);
}
if(r+1<n) {
ll a1=get(1,0,n-1,r);
ll a2=get(1,0,n-1,r+1);
ans-=f(a1,a2);
ans+=f(a1+x,a2);
}
add(1,0,n-1,l,r,x);
cout<<ans<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
3 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
284 ms |
7528 KB |
Output is correct |
2 |
Correct |
288 ms |
8080 KB |
Output is correct |
3 |
Correct |
284 ms |
8644 KB |
Output is correct |
4 |
Correct |
281 ms |
7780 KB |
Output is correct |
5 |
Correct |
291 ms |
8556 KB |
Output is correct |
6 |
Correct |
152 ms |
7964 KB |
Output is correct |
7 |
Correct |
148 ms |
7900 KB |
Output is correct |
8 |
Correct |
246 ms |
8864 KB |
Output is correct |
9 |
Correct |
249 ms |
9212 KB |
Output is correct |
10 |
Correct |
245 ms |
8044 KB |
Output is correct |
11 |
Correct |
168 ms |
7912 KB |
Output is correct |
12 |
Correct |
150 ms |
8304 KB |
Output is correct |
13 |
Correct |
150 ms |
8772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
3 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
3 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
3 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
284 ms |
7528 KB |
Output is correct |
23 |
Correct |
288 ms |
8080 KB |
Output is correct |
24 |
Correct |
284 ms |
8644 KB |
Output is correct |
25 |
Correct |
281 ms |
7780 KB |
Output is correct |
26 |
Correct |
291 ms |
8556 KB |
Output is correct |
27 |
Correct |
152 ms |
7964 KB |
Output is correct |
28 |
Correct |
148 ms |
7900 KB |
Output is correct |
29 |
Correct |
246 ms |
8864 KB |
Output is correct |
30 |
Correct |
249 ms |
9212 KB |
Output is correct |
31 |
Correct |
245 ms |
8044 KB |
Output is correct |
32 |
Correct |
168 ms |
7912 KB |
Output is correct |
33 |
Correct |
150 ms |
8304 KB |
Output is correct |
34 |
Correct |
150 ms |
8772 KB |
Output is correct |
35 |
Correct |
299 ms |
7508 KB |
Output is correct |
36 |
Correct |
295 ms |
9160 KB |
Output is correct |
37 |
Correct |
298 ms |
9796 KB |
Output is correct |
38 |
Correct |
294 ms |
9584 KB |
Output is correct |
39 |
Correct |
292 ms |
9588 KB |
Output is correct |
40 |
Correct |
292 ms |
9532 KB |
Output is correct |
41 |
Correct |
287 ms |
9412 KB |
Output is correct |
42 |
Correct |
290 ms |
9540 KB |
Output is correct |
43 |
Correct |
290 ms |
8812 KB |
Output is correct |
44 |
Correct |
293 ms |
9156 KB |
Output is correct |
45 |
Correct |
292 ms |
8948 KB |
Output is correct |
46 |
Correct |
293 ms |
9576 KB |
Output is correct |
47 |
Correct |
154 ms |
8516 KB |
Output is correct |
48 |
Correct |
156 ms |
8680 KB |
Output is correct |
49 |
Correct |
278 ms |
8792 KB |
Output is correct |
50 |
Correct |
165 ms |
8516 KB |
Output is correct |
51 |
Correct |
148 ms |
8556 KB |
Output is correct |
52 |
Correct |
185 ms |
8516 KB |
Output is correct |