Submission #707062

#	Time	Username	Problem	Language	Result	Execution time	Memory
707062		lam	Progression (NOI20_progression)	C++14	100 / 100	1500 ms	119488 KiB

Progression

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = (int)1e18;
const int maxn = 3e5 + 10;
int n,m;
int D[maxn];
struct node
{
    int pre,suf,val_l,val_r,sz,ans;
};
node hop(node x, node y)
{
    if (x.val_l==-1e18) return y;
    if (y.val_l==-1e18) return x;
    node cur;
    cur.sz=x.sz+y.sz;
    cur.ans=max(x.ans,y.ans);
    if (x.val_r==y.val_l) cur.ans=max(cur.ans,x.suf+y.pre);
    cur.val_l=x.val_l; cur.val_r=y.val_r;
    cur.pre = x.pre;
    if (x.sz==x.pre&&x.val_r==y.val_l) cur.pre=max(cur.pre,x.sz+y.pre);
    else cur.pre=x.pre;
    cur.suf = y.suf;
    if (y.sz==y.suf&&x.val_r==y.val_l) cur.suf=max(cur.suf,y.sz+x.suf);
    return cur;
}
node none = {0,0,-inf,-inf,0,0};
struct segtree
{
    node f[4*maxn]; int lazysum[4*maxn], lazyeq[4*maxn];
    void pushsum(int x, int lx, int rx, int val)
    {
        f[x].val_l+=val; f[x].val_r+=val;
        lazysum[x]+=val;
    }
    void pusheq(int x, int lx, int rx, int val)
    {
        f[x].val_l=f[x].val_r=lazyeq[x]=val;
        f[x].ans=f[x].pre=f[x].suf=f[x].sz=rx-lx+1;
        lazysum[x]=0;
    }
    void down(int x, int lx, int rx)
    {
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        if (lazyeq[x]!=-1e18)
        {
            pusheq(2*x,lx,mid,lazyeq[x]);
            pusheq(2*x+1,mid+1,rx,lazyeq[x]);
            lazyeq[x]=-1e18;
        }
        if (lazysum[x]!=0)
        {
            pushsum(2*x,lx,mid,lazysum[x]);
            pushsum(2*x+1,mid+1,rx,lazysum[x]);
            lazysum[x]=0;
        }
    }

    void build(int x, int lx, int rx)
    {
        lazysum[x]=0;
        lazyeq[x]=-1e18;
        if (lx==rx)
        {
            pusheq(x,lx,rx,D[lx]-D[lx-1]);
            return;
        }
        int mid=(lx+rx)/2;
        build(2*x,lx,mid); build(2*x+1,mid+1,rx);
        f[x]=hop(f[2*x],f[2*x+1]);
    }

    void add(int x, int lx, int rx, int l, int r, int val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            pushsum(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        add(2*x,lx,mid,l,r,val);
        add(2*x+1,mid+1,rx,l,r,val);
        f[x]=hop(f[2*x],f[2*x+1]);
    }
    void update_eq(int x, int lx, int rx, int l, int r, int val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            pusheq(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        update_eq(2*x,lx,mid,l,r,val);
        update_eq(2*x+1,mid+1,rx,l,r,val);
        f[x]=hop(f[2*x],f[2*x+1]);
    }
    void update(int x, int lx, int rx, int idx, int val)
    {
        if (lx==rx)
        {
            pusheq(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        if (idx<=mid) update(2*x,lx,mid,idx,val);
        else update(2*x+1,mid+1,rx,idx,val);
        f[x]=hop(f[2*x],f[2*x+1]);
    }
    node get(int x, int lx, int rx, int l, int r)
    {
        if (lx>r||rx<l) return {0,0,-inf,-inf,0,0};
        if (lx>=l&&rx<=r) return f[x];
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        return hop(get(2*x,lx,mid,l,r),get(2*x+1,mid+1,rx,l,r));
    }
    void dbg(int x, int lx, int rx)
    {
        cout<<x<<' '<<lx<<' '<<rx<<" = "<<f[x].val_l<<' '<<f[x].val_r<<" , "<<f[x].pre<<' '<<f[x].suf<<" , "<<f[x].sz<<' '<<f[x].ans<<'\n';
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        dbg(2*x,lx,mid); dbg(2*x+1,mid+1,rx);
    }
};
segtree tree;
struct line
{
    int a,b;
};
int calc(line x, int idx)
{
    return x.a*idx + x.b;
}
struct lichao_tree
{
    line f[4*maxn],lazysum[4*maxn],lazyeq[4*maxn];
    void pushsum(int x, int lx, int rx, line val)
    {
        f[x].a+=val.a; f[x].b+=val.b;
        lazysum[x].a+=val.a; lazysum[x].b+=val.b;
    }
    void pusheq(int x, int lx, int rx, line val)
    {
        f[x]=lazyeq[x]=val; lazysum[x]={0,0};
    }
    void down(int x, int lx, int rx)
    {
        if (lx==rx) return;
        int mid=(lx+rx)/2;
        if (lazyeq[x].a!=-inf||lazyeq[x].b!=-inf)
        {
            pusheq(2*x,lx,mid,lazyeq[x]);
            pusheq(2*x+1,mid+1,rx,lazyeq[x]);
            lazyeq[x]={-inf,-inf};
        }
        if (lazysum[x].a!=0||lazysum[x].b!=0)
        {
            pushsum(2*x,lx,mid,lazysum[x]);
            pushsum(2*x+1,mid+1,rx,lazysum[x]);
            lazysum[x]={0,0};
        }
    }
    void build(int x, int lx, int rx)
    {
        lazysum[x]={0,0};
        lazyeq[x]={-inf,-inf};
        if (lx==rx)
        {
            pusheq(x,lx,rx,{0,D[lx]});
            return;
        }
        int mid=(lx+rx)/2;
        build(2*x,lx,mid); build(2*x+1,mid+1,rx);
    }
    void add(int x, int lx, int rx, int l, int r, line val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            pushsum(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        add(2*x,lx,mid,l,r,val);
        add(2*x+1,mid+1,rx,l,r,val);
    }
    void update_eq(int x, int lx, int rx, int l, int r, line val)
    {
        if (lx>r||rx<l) return;
        if (lx>=l&&rx<=r)
        {
            pusheq(x,lx,rx,val);
            return;
        }
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        update_eq(2*x,lx,mid,l,r,val);
        update_eq(2*x+1,mid+1,rx,l,r,val);
    }
    line get(int x, int lx, int rx, int idx)
    {
        if (lx==rx) return f[x];
        int mid=(lx+rx)/2;
        down(x,lx,rx);
        if (idx<=mid) return get(2*x,lx,mid,idx);
        else return get(2*x+1,mid+1,rx,idx);
    }
};
lichao_tree lichao;

void sub1()
{
    for (int i=1; i<=m; i++)
    {
        int t; cin>>t;
        if (t==1||t==2)
        {
            int l,r,x,y; cin>>l>>r>>x>>y;
        }
        else
        {
            int l,r; cin>>l>>r;
            cout<<"1\n";
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>D[i];
    if (n==1)
    {
        sub1();
        return 0;
    }
    tree.build(1,2,n);
    lichao.build(1,1,n);
    for (int i=1; i<=m; i++)
    {
        int t; cin>>t;
        if (t==1)
        {
            int l,r,S,C; cin>>l>>r>>S>>C;
            line temp = {C,S-l*C};
            tree.add(1,2,n,l+1,r,C);
            lichao.add(1,1,n,l,r,temp);
            if (l>1) tree.update(1,2,n,l,calc(lichao.get(1,1,n,l),l) - calc(lichao.get(1,1,n,l-1),l-1));
            if (r<n) tree.update(1,2,n,r+1,calc(lichao.get(1,1,n,r+1),r+1) - calc(lichao.get(1,1,n,r),r));
        }
        else if (t==2)
        {
            int l,r,S,C; cin>>l>>r>>S>>C;
            line temp = {C,S-l*C};
            tree.update_eq(1,2,n,l+1,r,C);
            lichao.update_eq(1,1,n,l,r,temp);
            if (l>1) tree.update(1,2,n,l,calc(lichao.get(1,1,n,l),l) - calc(lichao.get(1,1,n,l-1),l-1));
            if (r<n) tree.update(1,2,n,r+1,calc(lichao.get(1,1,n,r+1),r+1) - calc(lichao.get(1,1,n,r),r));
        }
        else
        {
            int l,r; cin>>l>>r;
            node ans = tree.get(1,2,n,l+1,r);
            cout<<ans.ans+1<<'\n';
        }
//        tree.dbg(1,2,n);
    }
}

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