#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=(1<<18);
ll t[2*maxn+1];//wyniki
pair<bool,bool>bb[2*maxn+1];//w ktora strone
pair<ll,ll>tp[2*maxn+1];//krancowe wartosci
ll l[2*maxn+1];//ile zepchnac w dol
pair<int,int>p[2*maxn+1];
void prz(int v,int x,int y){
p[v]={x,y};
if(x==y)return;
prz(2*v,x,(x+y)/2);
prz(2*v+1,(x+y)/2+1,y);
return;
}
void lazy(int v){
tp[2*v].first+=l[v];
tp[2*v].second+=l[v];
tp[2*v+1].first+=l[v];
tp[2*v+1].second+=l[v];
l[2*v]+=l[v];
l[2*v+1]+=l[v];
l[v]=0;
return;
}
void dodaj(int v,int a,int b,ll x){
if(a>p[v].second||b<p[v].first)return;
if(a<=p[v].first&&b>=p[v].second){
tp[v].first+=x;
tp[v].second+=x;
l[v]+=x;
return;
}
lazy(v);
dodaj(2*v,a,b,x);
dodaj(2*v+1,a,b,x);
tp[v].first=tp[2*v].first;
tp[v].second=tp[2*v+1].second;
t[v]=t[2*v]+t[2*v+1];
if(p[2*v].first==p[2*v].second){
if(tp[v].first<tp[v].second)bb[v]={0,0};//0 = rosnacy, 1 = malejacy
else bb[v]={1,1};
t[v]=max(tp[2*v].second,tp[2*v+1].first)-min(tp[2*v].second,tp[2*v+1].first);
// cout<<"pomoc: "<<t[v]<<' '<<bb[v].first<<' '<<bb[v].second<<'\n';
}
else{
bb[v]={bb[2*v].first,bb[2*v+1].second};
if(tp[2*v].second<tp[2*v+1].first&&bb[2*v].second==0&&bb[2*v+1].first==0)t[v]+=tp[2*v+1].first-tp[2*v].second;
if(tp[2*v].second>tp[2*v+1].first&&bb[2*v].second==1&&bb[2*v+1].first==1)t[v]+=tp[2*v].second-tp[2*v+1].first;
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
prz(1,0,maxn-1);
ll n,q,v1,v2,v3,ost;
cin>>n>>q;
for(int i=0;i<n;i++){
cin>>v1;
ost=v1;
dodaj(1,i,i,v1);
}
dodaj(1,n,maxn-1,ost);
//cout<<t[1]<<'\n';
while(q--){
cin>>v1>>v2>>v3;
if(v2==n)v2=maxn;
dodaj(1,v1-1,v2-1,v3);
cout<<t[1]<<'\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:66:7: warning: 'ost' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | dodaj(1,n,maxn-1,ost);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
