Submission #960335

#TimeUsernameProblemLanguageResultExecution timeMemory
960335boyliguanhanProgression (NOI20_progression)C++17
100 / 100
1422 ms125200 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #pragma GCC optimize(2) int Q=1e18; struct Ln{ int k,b; Ln(){k=b=0;} Ln(int x,int y){k=x,b=y;} friend Ln ad(Ln a, Ln b){return Ln(a.k+b.k,a.b+b.b);} int operator()(int x){ return k*x+b; } }; struct node{ Ln V,S,A; node*lc,*rc; node(){A=Ln(),S=Ln(Q,0),lc=rc=0;} void mc(){ if(!lc)lc=new node(); if(!rc)rc=new node(); } void push(){ if(S.k!=Q) if(lc) lc->A=rc->A=Ln(),lc->S=rc->S=S,S.k=Q; if(A.k||A.b) if(lc) lc->A=ad(A,lc->A),rc->A=ad(A,rc->A),A=Ln(); } }*rt; int lcq(node*rt,int l,int r,int pos){ if(l-r) rt->mc(); if(l==r) return ad(rt->A,rt->S)(pos); rt->push(); if(l+r>>1<pos) return lcq(rt->rc,l+r+2>>1,r,pos); return lcq(rt->lc,l,l+r>>1,pos); } void lcua(node*rt,int l,int r,int tl,int tr,Ln x){ if(l-r) rt->mc(); if(l>tr||tl>r) return; if(tl<=l&&r<=tr) return rt->A=ad(rt->A,x),(l-r?rt->push():void()); rt->push(); lcua(rt->lc,l,l+r>>1,tl,tr,x); lcua(rt->rc,l+r+2>>1,r,tl,tr,x); } void lcus(node*rt,int l,int r,int tl,int tr,Ln x){ if(l-r) rt->mc(); if(l>tr||tl>r) return; if(tl<=l&&r<=tr) return rt->S=x,rt->A=Ln(),(l-r?rt->push():void()); rt->push(); lcus(rt->lc,l,l+r>>1,tl,tr,x); lcus(rt->rc,l+r+2>>1,r,tl,tr,x); } struct tp2{ int FE,LE,ans,fans,lans,sz; tp2(int V,int s){FE=LE=V,ans=fans=lans=sz=s;} tp2(tp2 a,tp2 b){ FE=(a.sz?a.FE:b.FE),LE=(b.sz?b.LE:a.LE); fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans); lans=(b.ans==b.sz&&LE==a.LE||!b.sz?b.sz+a.lans:b.lans); ans=max({a.ans,b.ans,(a.LE==b.FE)*(a.lans+b.fans)}); sz=a.sz+b.sz; } }; struct node2{ tp2 V=tp2(0ll,1ll); int A=0,S=Q; node2(int v){V=tp2(v,1ll);} node2(){} } T[1<<20]; void pd(int i,bool b){ if(T[i].S!=Q){ T[i].V=tp2(T[i].S,T[i].V.sz); if(b) T[i*2].S=T[i*2+1].S=T[i].S,T[i*2].A=T[i*2+1].A=0; } if(T[i].A){ T[i].V.FE+=T[i].A,T[i].V.LE+=T[i].A; if(b) T[i*2].A+=T[i].A,T[i*2+1].A+=T[i].A; } T[i].A=0,T[i].S=Q; } tp2 segq(int i,int l,int r,int tl,int tr){ pd(i,l-r); if(tl<=l&&r<=tr) return T[i].V; if(l>tr||tl>r) return tp2(0,0); return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr)); } void segua(int i,int l,int r,int tl,int tr,int X){ pd(i,l-r); if(tl<=l&&r<=tr) return T[i].A+=X,pd(i,l-r); if(l>tr||tl>r) return; segua(i*2,l,l+r>>1,tl,tr,X); segua(i*2+1,l+r+2>>1,r,tl,tr,X); T[i].V=tp2(T[i*2].V,T[i*2+1].V); } void segus(int i,int l,int r,int tl,int tr,int X){ pd(i,l-r); if(tl<=l&&r<=tr) return T[i].A=0,T[i].S=X,pd(i,l-r); if(l>tr||tl>r) return; segus(i*2,l,l+r>>1,tl,tr,X); segus(i*2+1,l+r+2>>1,r,tl,tr,X); T[i].V=tp2(T[i*2].V,T[i*2+1].V); } int bruh[5<<16],n; void maintain(int id){ segus(1,1,n-1,id,id,lcq(rt,1,n,id+1)-lcq(rt,1,n,id)); } signed main(){ cin.tie(0)->sync_with_stdio(0); int m; rt=new node(); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>bruh[i]; lcus(rt,1,n,i,i,Ln(0,bruh[i])); } for(int i=1;i<n;i++) segus(1,1,n-1,i,i,bruh[i+1]-bruh[i]); while(m--){ int t,l,r,s,c; cin>>t>>l>>r; if(t>2){ cout<<(n-1?segq(1,1,n-1,l,r-1).ans+1:1)<<'\n'; continue; } cin>>s>>c; if(t<2){ lcua(rt,1,n,l,r,Ln(c,s-l*c)); segua(1,1,n-1,l,r-1,c); } else { lcus(rt,1,n,l,r,Ln(c,s-l*c)); segus(1,1,n-1,l,r-1,c); } if(l>1) maintain(l-1); if(r<n) maintain(r); } }

Compilation message (stderr)

Progression.cpp: In function 'long long int lcq(node*, long long int, long long int, long long int)':
Progression.cpp:35:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     if(l+r>>1<pos)
      |        ~^~
Progression.cpp:36:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         return lcq(rt->rc,l+r+2>>1,r,pos);
      |                           ~~~^~
Progression.cpp:37:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     return lcq(rt->lc,l,l+r>>1,pos);
      |                         ~^~
Progression.cpp: In function 'void lcua(node*, long long int, long long int, long long int, long long int, Ln)':
Progression.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     lcua(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     lcua(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In function 'void lcus(node*, long long int, long long int, long long int, long long int, Ln)':
Progression.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     lcus(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     lcus(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In constructor 'tp2::tp2(tp2, tp2)':
Progression.cpp:62:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp:63:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   63 |         lans=(b.ans==b.sz&&LE==a.LE||!b.sz?b.sz+a.lans:b.lans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp: In function 'tp2 segq(long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:91:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                           ~^~
Progression.cpp:91:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                                                    ~~~^~
Progression.cpp: In function 'void segua(long long int, long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     segua(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:99:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     segua(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~
Progression.cpp: In function 'void segus(long long int, long long int, long long int, long long int, long long int, long long int)':
Progression.cpp:107:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |     segus(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:108:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |     segus(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~
#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...