Submission #1045351

#TimeUsernameProblemLanguageResultExecution timeMemory
1045351KarolZSjeckanje (COCI21_sjeckanje)C++14
0 / 110
3 ms16988 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...