Submission #265349

#TimeUsernameProblemLanguageResultExecution timeMemory
265349eohomegrownappsProgression (NOI20_progression)C++14
0 / 100
3157 ms939768 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int deltas[400000]; struct Data{ int len = 1; int maxpref=1; int maxsuff=1; ll prefval=0; ll suffval=0; int maxlen=1; ll deltasum = 0; }; int n; int ncnt=0; Data combine(const Data &l, const Data &r){ Data ans; ans.len = l.len + r.len; ans.deltasum = l.deltasum + r.deltasum; ans.maxpref = l.maxpref; ans.prefval = l.prefval; ans.maxsuff = r.maxsuff; ans.suffval = r.suffval; if (l.maxpref==l.len&&l.prefval==r.prefval){ ans.maxpref=l.len+r.maxpref; } if (r.maxpref==r.len&&r.prefval==l.suffval){ ans.maxsuff=r.len+l.maxsuff; } ans.maxlen=max(l.maxlen,r.maxlen); if (l.suffval==r.prefval){ ans.maxlen=max(ans.maxlen,l.maxsuff+r.maxpref); } return ans; } Data init(ll ind){ Data ans; ans.prefval = deltas[ind]; ans.suffval = deltas[ind]; ans.deltasum = deltas[ind]; return ans; } struct Node{ int s,e; Data v; Node *l, *r; ll lazyval = 0; bool doreplace = false; Node(ll _s, ll _e){ ncnt++; if (ncnt>=5000000){ while (true){continue;} } s=_s;e=_e; //cout<<s<<' '<<e<<'\n'; if (s==e){ v = init(s); return; } int m = (s+e)/2; l = new Node(s,m); r = new Node(m+1,e); v = combine(l->v, r->v); } void propagate(){ //cout<<"propagate "<<s<<' '<<e<<'\n'; //cout<<"lazy: "<<lazyval<<' '<<doreplace<<'\n'; if (doreplace){ v.prefval = lazyval; v.suffval = lazyval; v.deltasum = v.len * lazyval; v.maxpref = v.len; v.maxsuff = v.len; v.maxlen = v.len; } else { v.prefval+=lazyval; v.suffval+=lazyval; v.deltasum+=v.len * lazyval; } if (s!=e){ if (doreplace){ l->doreplace = true; l->lazyval = lazyval; r->doreplace = true; r->lazyval = lazyval; } else { l->lazyval+=lazyval; r->lazyval+=lazyval; } } lazyval=0; doreplace=false; } Data query(ll a, ll b){ assert(a<=b); assert(b<=n-2); int m = (s+e)/2; propagate(); if (a==s&&b==e){ return v; } if (b<=m){ return l->query(a,b); } else if (m<a){ return r->query(a,b); } else { return combine(l->query(a,m),r->query(m+1,b)); } } void update(ll a, ll b, ll val, bool replace){ assert(b<=n-2); int m = (s+e)/2; //cout<<"update "<<a<<' '<<b<<' '<<val<<' '<<replace<<'\n'; assert(a<=b); if (a==s&&b==e){ if (replace){ doreplace=true; lazyval=val; } else { lazyval+=val; } return; } propagate(); if (b<=m){ l->update(a,b,val,replace); } else if (m<a){ r->update(a,b,val,replace); } else { l->update(a,m,val,replace); r->update(m+1,b,val,replace); } l->propagate(); r->propagate(); v = combine(l->v,r->v); } }; ll x0; Node *root; void patch(ll l, ll r, ll s, ll c){ if (l==0){ x0+=s; } else { root->update(l-1,l-1,s,false); } if (l<=r-1){ root->update(l,r-1,c,false); } if (r!=n-1){ root->update(r,r,-s-(r-l)*c,false); } } ll getDelta(ll ind){ Data dxl = root->query(ind,ind); return dxl.deltasum; } ll getVal(ll ind){ if (ind==0){ return x0; } Data dxl = root->query(0,ind-1); ll ans = x0+dxl.deltasum; return ans; } void rewrite(ll l, ll r, ll s, ll c){ ll xr1=0; if (r!=n-1){ xr1 = getVal(r+1); } if (l==0){ x0=s; } else { ll xlm1 = getVal(l-1); root->update(l-1,l-1,s-xlm1,true); } if (l<=r-1){ root->update(l,r-1,c,true); } if (r!=n-1){ root->update(r,r,xr1-s-(r-l)*c,true); } } ll evaluate(ll l, ll r){ if (l==r){ return 1; } Data d = root->query(l,r-1); return d.maxlen+1; } int main(){ //cin.tie(0); //ios_base::sync_with_stdio(0); ll q; cin>>n>>q; cin>>x0; ll xprev = x0; for (ll i = 1; i<n; i++){ ll xnew; cin>>xnew; deltas[i-1]=xnew-xprev; xprev=xnew; } root = new Node(0,n-2); /*for (ll i = 0; i<n-1; i++){ cout<<getDelta(i)<<' '; }cout<<'\n'; for (ll i = 0; i<n; i++){ cout<<getVal(i)<<' '; }cout<<'\n';*/ for (ll i = 0; i<q; i++){ ll t; cin>>t; ll l,r,s,c; if (t==1){ cin>>l>>r>>s>>c; patch(l-1,r-1,s,c); /*for (ll i = 0; i<n-1; i++){ cout<<getDelta(i)<<' '; }cout<<'\n'; for (ll i = 0; i<n; i++){ cout<<getVal(i)<<' '; }cout<<'\n';*/ } else if (t==2){ cin>>l>>r>>s>>c; rewrite(l-1,r-1,s,c); /*for (ll i = 0; i<n-1; i++){ cout<<getDelta(i)<<' '; }cout<<'\n'; for (ll i = 0; i<n; i++){ cout<<getVal(i)<<' '; }cout<<'\n';*/ } else if (t==3){ cin>>l>>r; cout<<evaluate(l-1,r-1)<<'\n'; } else { continue; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...