#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l + r)>>1) + 1,r
#define pii pair<int,int>
#define int ll
using namespace std;
const int N = 2e5 + 5;
int a[N],A[N],b[N],S,T;
int getans(int x,int y){
if (x < y) return -S*(y-x);
return (x - y)*T;
}
void upd(int h,int l,int r,int L,int R,int val){
//neli
for (int i = L; i <= R; i++)
b[i] += val;
}
int get(int h,int l,int r,int idx){
return b[idx];
}
void UPD(int h,int l,int r,int L,int R,int val){
for (int i = L; i <= R; i++)
A[i] += val;
}
int GET(int h,int l,int r,int idx){
return A[idx];
}
signed main (){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,q;
cin>>n>>q>>S>>T;
++n;
for (int i = 1; i <= n; i++){
cin >> a[i];
int val = getans(a[i - 1],a[i]);
upd(1,1,n,i,n,val);
UPD(1,1,n,i,i,a[i]);
}
while (q--){
int l,r,x;
cin>>l>>r>>x;
l++,r++;
UPD(1,1,n,l,r,x);
int newx = GET(1,1,n,l - 1);
int newy = GET(1,1,n,l);
int oldx = newx;
int oldy = newy - x;
int oldval = getans(oldx,oldy);
int newval = getans(newx,newy);
upd(1,1,n,l,n,newval - oldval);
if (r + 1 <= n){
newx = GET(1,1,n,r);
newy = GET(1,1,n,r+1);
oldx = newx - x;
oldy = newy;
oldval = getans(oldx,oldy);
newval = getans(newx,newy);
upd(1,1,n,r+1,n,newval - oldval);
}
cout<<get(1,1,n,n)<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4444 KB |
Output is correct |
2 |
Correct |
7 ms |
4444 KB |
Output is correct |
3 |
Correct |
7 ms |
4572 KB |
Output is correct |
4 |
Correct |
7 ms |
4444 KB |
Output is correct |
5 |
Correct |
7 ms |
4444 KB |
Output is correct |
6 |
Correct |
7 ms |
4444 KB |
Output is correct |
7 |
Correct |
7 ms |
4444 KB |
Output is correct |
8 |
Correct |
7 ms |
4444 KB |
Output is correct |
9 |
Correct |
7 ms |
4444 KB |
Output is correct |
10 |
Correct |
7 ms |
4444 KB |
Output is correct |
11 |
Correct |
7 ms |
4652 KB |
Output is correct |
12 |
Correct |
7 ms |
4444 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
7 ms |
4648 KB |
Output is correct |
15 |
Correct |
7 ms |
4440 KB |
Output is correct |
16 |
Correct |
8 ms |
4696 KB |
Output is correct |
17 |
Correct |
8 ms |
4444 KB |
Output is correct |
18 |
Correct |
8 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1088 ms |
4768 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4444 KB |
Output is correct |
2 |
Correct |
7 ms |
4444 KB |
Output is correct |
3 |
Correct |
7 ms |
4572 KB |
Output is correct |
4 |
Correct |
7 ms |
4444 KB |
Output is correct |
5 |
Correct |
7 ms |
4444 KB |
Output is correct |
6 |
Correct |
7 ms |
4444 KB |
Output is correct |
7 |
Correct |
7 ms |
4444 KB |
Output is correct |
8 |
Correct |
7 ms |
4444 KB |
Output is correct |
9 |
Correct |
7 ms |
4444 KB |
Output is correct |
10 |
Correct |
7 ms |
4444 KB |
Output is correct |
11 |
Correct |
7 ms |
4652 KB |
Output is correct |
12 |
Correct |
7 ms |
4444 KB |
Output is correct |
13 |
Correct |
8 ms |
4648 KB |
Output is correct |
14 |
Correct |
7 ms |
4648 KB |
Output is correct |
15 |
Correct |
7 ms |
4440 KB |
Output is correct |
16 |
Correct |
8 ms |
4696 KB |
Output is correct |
17 |
Correct |
8 ms |
4444 KB |
Output is correct |
18 |
Correct |
8 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4440 KB |
Output is correct |
22 |
Execution timed out |
1088 ms |
4768 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |