Submission #960331

#	Time	Username	Problem	Language	Result	Execution time	Memory
960331		boyliguanhan	Progression (NOI20_progression)	C++17	100 / 100	1516 ms	125156 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define int long long
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:34:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     if(l+r>>1<pos)
      |        ~^~
Progression.cpp:35:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         return lcq(rt->rc,l+r+2>>1,r,pos);
      |                           ~~~^~
Progression.cpp:36:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     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:44:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     lcua(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     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:53:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     lcus(rt->lc,l,l+r>>1,tl,tr,x);
      |                   ~^~
Progression.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     lcus(rt->rc,l+r+2>>1,r,tl,tr,x);
      |                 ~~~^~
Progression.cpp: In constructor 'tp2::tp2(tp2, tp2)':
Progression.cpp:61:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |         fans=(a.ans==a.sz&&FE==b.FE||!a.sz?a.sz+b.fans:a.fans);
      |               ~~~~~~~~~~~^~~~~~~~~~
Progression.cpp:62:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         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:90:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     return tp2(segq(i*2,l,l+r>>1,tl,tr),segq(i*2+1,l+r+2>>1,r,tl,tr));
      |                           ~^~
Progression.cpp:90:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     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:97:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     segua(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:98:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |     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:106:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     segus(i*2,l,l+r>>1,tl,tr,X);
      |                 ~^~
Progression.cpp:107:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |     segus(i*2+1,l+r+2>>1,r,tl,tr,X);
      |                 ~~~^~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17