Submission #706998

#	Time	Username	Problem	Language	Result	Execution time	Memory
706998		lam	Progression (NOI20_progression)	C++14	44 / 100	447 ms	77260 KiB

Progression

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second

int n,m;
int D[maxn];

struct node
{
    int pre,suf,val_l,val_r,ans,sz;
};
inline node hop(node x, node y)
{
    if (x.val_l==-1e18) return y;
    if (y.val_l==-1e18) return x;
    node z;
    z.pre = x.pre;
    if (x.pre==x.sz&&x.val_r==y.val_l) z.pre = max(z.pre,x.sz+y.pre);
    z.suf = y.suf;
    if (y.suf==y.sz&&y.val_l==x.val_r) z.suf = max(z.suf,y.sz+x.suf);
    z.val_l = x.val_l; z.val_r = y.val_r;
    z.ans = max(x.ans, y.ans);
    if (x.val_r==y.val_l) z.ans = max(z.ans,x.suf+y.pre);
    z.sz = x.sz + y.sz;
    return z;
}

node f[4*maxn]; int lazy_sum[4*maxn], lazy_eq[4*maxn];

void pusheq(int x, int lx, int rx, int val)
{
    f[x].val_l = f[x].val_r = lazy_eq[x] = val; lazy_sum[x]=0;
    f[x].ans = f[x].pre = f[x].suf = f[x].sz = (rx-lx+1);
}

void pushsum(int x, int lx, int rx, int val)
{
    f[x].val_l += val; f[x].val_r += val; lazy_sum[x] += val;
}

void down(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (lazy_eq[x]!=-1e18)
    {
        pusheq(2*x,lx,mid,lazy_eq[x]);
        pusheq(2*x+1,mid+1,rx,lazy_eq[x]);
        lazy_eq[x]=-1e18;
    }
    if (lazy_sum[x]!=0)
    {
        pushsum(2*x,lx,mid,lazy_sum[x]);
        pushsum(2*x+1,mid+1,rx,lazy_sum[x]);
        lazy_sum[x]=0;
    }
}

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,(int)-1e18,(int)-1e18,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));
}

struct line
{
    int a,b;
};
inline int calc(line x, int idx)
{
    return x.a*idx + x.b;
}
line seg[4*maxn],lazyeq[4*maxn],lazysum[4*maxn];

void pusheq_lichao(int x, int lx, int rx, line val)
{
    seg[x]=lazyeq[x]=val; lazysum[x]={0,0};
}
void pushsum_lichao(int x, int lx, int rx, line val)
{
    seg[x].a+=val.a; seg[x].b+=val.b;
    lazysum[x].a+=val.a; lazysum[x].b+=val.b;
}

void down_lichao(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (lazyeq[x].a!=-1e18)
    {
        pusheq_lichao(2*x,lx,mid,lazyeq[x]);
        pusheq_lichao(2*x+1,mid+1,rx,lazyeq[x]);
        lazyeq[x]={(int)-1e18,(int)-1e18};
    }
    if (lazysum[x].a!=0||lazysum[x].b!=0)
    {
        pushsum_lichao(2*x,lx,mid,lazysum[x]);
        pushsum_lichao(2*x+1,mid+1,rx,lazysum[x]);
        lazysum[x]={0,0};
    }
}

void add_lichao(int x, int lx, int rx, int l, int r, line val)
{
    if (lx>r||rx<l) return ;
    if (lx>=l&&rx<=r)
    {
        pushsum_lichao(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    add_lichao(2*x,lx,mid,l,r,val);
    add_lichao(2*x+1,mid+1,rx,l,r,val);
}

void update_lichao(int x, int lx, int rx, int l, int r, line val)
{
    if (lx>r||rx<l) return;
    if (lx>=l&&rx<=r)
    {
        pusheq_lichao(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    update_lichao(2*x,lx,mid,l,r,val);
    update_lichao(2*x+1,mid+1,rx,l,r,val);
}

line qry(int x, int lx, int rx, int idx)
{
    if (lx==rx) return seg[x];
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    if (idx<=mid) return qry(2*x,lx,mid,idx);
    else return qry(2*x+1,mid+1,rx,idx);
}

void build(int x, int lx, int rx)
{
    lazy_eq[x]=-1e18;
    lazy_sum[x]=0;
    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 build_lichao(int x, int lx, int rx)
{
    lazyeq[x]={(int)-1e18,(int)-1e18};
    lazysum[x]={0,0};
    if (lx==rx)
    {
        pusheq_lichao(x,lx,rx,{0,D[lx]});
        return;
    }
    int mid=(lx+rx)/2;
    build_lichao(2*x,lx,mid); build_lichao(2*x+1,mid+1,rx);
}

//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<<" :: "<<lazy_eq[x]<<' '<<lazy_sum[x]<<'\n';
//    if (lx==rx) return;
//    int mid=(lx+rx)/2;
//    dbg(2*x,lx,mid);
//    dbg(2*x+1,mid+1,rx);
//}
//void dbg_lichao(int x, int lx, int rx)
//{
//    cout<<x<<' '<<lx<<' '<<rx<<" = "<<seg[x].a<<' '<<seg[x].b<<" , "<<lazysum[x].a<<' '<<lazysum[x].b<<" , "<<lazyeq[x].a<<' '<<lazyeq[x].b<<'\n';
//    if (lx==rx) return;
//    int mid=(lx+rx)/2;
//    dbg_lichao(2*x,lx,mid);
//    dbg_lichao(2*x+1,mid+1,rx);
//}

void sub1()
{
    for (int i=1; i<=m; i++)
    {
        int t,l,r; cin>>t;
        if (t==1||t==2)
        {
            int x,y; cin>>l>>r>>x>>y;
        }
        else
        {
            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;
    }
    build(1,2,n);
//    build_lichao(1,1,n);
    bool has=0;
    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};
//            add(1,2,n,l+1,r,C);
//            add_lichao(1,1,n,l,r,temp);
//            if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
//            if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
//            cout<<l<<" :: "<<calc(qry(1,1,n,l),l)<<'\n';
//            cout<<r<<" :: "<<calc(qry(1,1,n,r),r)<<'\n';
        }
        else if (t==2)
        {
            int l,r,S,C; cin>>l>>r>>S>>C;
            has=1;
//            line temp = {C, S-l*C};
//            update_eq(1,2,n,l+1,r,C);
//            update_lichao(1,1,n,l,r,temp);
//            if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
//            if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
        }
        else
        {
            int l,r; cin>>l>>r;
            if (has)
            {
                cout<<r-l+1<<'\n';
                continue;
            }
            node temp = get(1,2,n,l+1,r);
            int ans = temp.ans + 1;
            cout<<ans<<'\n';
        }
//        dbg(1,2,n);
//        cout<<" ========= \n";
//        dbg_lichao(1,1,n);
//        cout<<"---------------------------\n";
//        cout<<"---------------------------\n";
//        cout<<"---------------------------\n";
    }
}
/**
10 3
1 2 3 4 1 2 3 4 5 5
3 1 10
1 2 8 1 2
3 2 9
2 1 10 3 4
3 1 10
**/

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