typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
struct Seg{
int n;
vector<ll>sum,ek,arr;
vector<int>sol,sag;
void comb(int node,int left,int right){
sum[node]=sum[node*2]+sum[node*2+1];
ek[node]=ek[node*2];
sol[node]=sol[node*2];
if(sol[node*2]==0)sol[node]=sol[node*2+1];
sag[node]=sag[node*2+1];
if(sag[node*2+1]==0)sag[node]=sag[node*2];
if(sol[node*2+1]+sag[node*2]){
sum[node]+=ek[node*2+1];
}
}
void build(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
sum[node]=0;
if(arr[left]<0)sol[node]=-1;
if(arr[left]==0)sol[node]=0;
if(arr[left]>0)sol[node]=1;
sag[node]=sol[node];
ek[node]=abs(arr[left]);
return;
}
build(node*2,left,mid);build(node*2+1,mid+1,right);
comb(node,left,right);
}
Seg(vector<ll>v){
arr=v;
n=arr.size();
sum.resize(n<<2);
ek.resize(n<<2);
sol.resize(n<<2);
sag.resize(n<<2);
build();
}
ll tar,x;
void up(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
arr[left]+=x;
sum[node]=0;
if(arr[left]<0)sol[node]=-1;
if(arr[left]==0)sol[node]=0;
if(arr[left]>0)sol[node]=1;
sag[node]=sol[node];
ek[node]=abs(arr[left]);
return;
}
if(tar>mid)up(node*2+1,mid+1,right);
else up(node*2,left,mid);
comb(node,left,right);
}
void update(ll l,ll r){
tar=l;
x=r;
up();
}
};
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int n,q;cin>>n>>q;
vector<ll>v;
ll las;cin>>las;v.pb(0);
for(int i=1;i<n;i++){
ll x;cin>>x;
v.pb(x-las);
las=x;
}
Seg seg(v);
while(q--){
int l,r;ll x;
cin>>l>>r>>x;
if(l!=1){
seg.update(l-1,x);
}
if(r!=n){
seg.update(r,-x);
}
cout<<seg.sum[1]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
