Submission #1088556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088556		vjudge1	Progression (NOI20_progression)	C++17	100 / 100	1098 ms	122196 KiB

Progression

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn=3e5+3;
const int INF=LLONG_MAX;
int n,q,a[maxn],b[maxn];
struct segtree
{
    int sett[4*maxn],add[4*maxn],mul[4*maxn];
    void cons(int id,int cl,int cr)
    {
        if(cl==cr)
        {
            sett[id]=a[cl];
            add[id]=0;
            mul[id]=0;
            return;
        }
        int mid=(cl+cr)/2;
        cons(2*id,cl,mid);
        cons(2*id+1,mid+1,cr);
        add[id]=mul[id]=0;
        sett[id]=INF;
    }
    void down(int id)
    {
        if(sett[id]!=INF)
        {
            sett[2*id]=sett[id*2+1]=sett[id];
            add[2*id]=add[id*2+1]=0;
            mul[2*id]=mul[id*2+1]=0;
            sett[id]=INF;
        }
        add[id*2]+=add[id];
        add[id*2+1]+=add[id];
        add[id]=0;
        mul[id*2]+=mul[id];
        mul[id*2+1]+=mul[id];
        mul[id]=0;
    }
    void updateset(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            sett[id]=val;
            add[id]=0;
            mul[id]=0;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updateset(2*id,cl,mid,l,r,val);
        updateset(2*id+1,mid+1,cr,l,r,val);
    }
    void updateadd(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            add[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updateadd(2*id,cl,mid,l,r,val);
        updateadd(2*id+1,mid+1,cr,l,r,val);
    }
    void updatemul(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            mul[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updatemul(2*id,cl,mid,l,r,val);
        updatemul(2*id+1,mid+1,cr,l,r,val);
    }
    int get(int id,int cl,int cr,int pos)
    {
        if(cl==cr)
        {
//            if(sett[id]==INF) return add[id]+pos*mul[id];
            return sett[id]+add[id]+pos*mul[id];
        }
        int mid=(cl+cr)/2;
        down(id);
        if(pos<=mid) return get(2*id,cl,mid,pos);
        else return get(2*id+1,mid+1,cr,pos);
    }
}f;
struct node
{
    pii pre,suf,opt;
    int l;
};
node operator +(node a,node b)
{
    node res;
    res.l=a.l+b.l;
    if(a.l==0) return b;
    if(b.l==0) return a;
    if(a.pre.sc==a.l&&(a.pre.fi==b.pre.fi))
    {
        res.pre={a.pre.fi,a.l+b.pre.sc};
    }
    else res.pre=a.pre;
    if(b.suf.sc==b.l&&(b.suf.fi==a.suf.fi))
    {
        res.suf={b.suf.fi,b.l+a.suf.sc};
    }
    else res.suf=b.suf;
    res.opt=a.opt;
    if(res.opt.sc<b.opt.sc) res.opt=b.opt;
    if(a.suf.fi==b.pre.fi)
    {
        if(a.suf.sc+b.pre.sc>res.opt.sc)
        {
            res.opt={a.suf.fi,a.suf.sc+b.pre.sc};
        }
    }
    return res;
}
struct seggtree
{
    node ST[4*maxn];
    int laz[4*maxn],add[maxn*4];
    void down(int id)
    {
        if(laz[id]!=INF)
        {
            laz[id*2]=laz[id];
            laz[id*2+1]=laz[id];
            ST[id*2]={{laz[id],ST[id*2].l},{laz[id],ST[id*2].l},{laz[id],ST[id*2].l},ST[id*2].l};
            ST[id*2+1]={{laz[id],ST[id*2+1].l},{laz[id],ST[id*2+1].l},{laz[id],ST[id*2+1].l},ST[id*2+1].l};
            add[id*2]=add[2*id+1]=0;
            laz[id]=INF;
        }
        {
            ST[id*2].pre.fi+=add[id];
            ST[id*2].opt.fi+=add[id];
            ST[id*2].suf.fi+=add[id];
            ST[id*2+1].pre.fi+=add[id];
            ST[id*2+1].opt.fi+=add[id];
            ST[id*2+1].suf.fi+=add[id];
            add[2*id]+=add[id];
            add[2*id+1]+=add[id];
            add[id]=0;
        }
    }
    void cons(int id,int cl,int cr)
    {
        if(cl==cr)
        {
            ST[id]={{b[cl],1},{b[cl],1},{b[cl],1},1};
            laz[id]=b[cl];
            return;
        }
        int mid=(cl+cr)/2;
        cons(2*id,cl,mid);
        cons(2*id+1,mid+1,cr);
        ST[id]=ST[id*2]+ST[id*2+1];
        laz[id]=INF;
    }
    void update(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            ST[id].opt.fi+=val;
            ST[id].pre.fi+=val;
            ST[id].suf.fi+=val;
            add[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        update(2*id,cl,mid,l,r,val);
        update(2*id+1,mid+1,cr,l,r,val);
        ST[id]=ST[id*2]+ST[id*2+1];
    }
    void rupdate(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            laz[id]=val;
            add[id]=0;
            ST[id]={{laz[id],ST[id].l},{laz[id],ST[id].l},{laz[id],ST[id].l},ST[id].l};
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        rupdate(2*id,cl,mid,l,r,val);
        rupdate(2*id+1,mid+1,cr,l,r,val);
        ST[id]=ST[id*2]+ST[id*2+1];
    }
    node get(int id,int cl,int cr,int l,int r)
    {
        if(cl>r||cr<l) return {{0,0},{0,0},{0,0},0};
        if(cl>=l&&cr<=r) return ST[id];
        int mid=(cl+cr)/2;
        down(id);
        node siu=get(2*id,cl,mid,l,r)+get(2*id+1,mid+1,cr,l,r);
        return siu;
    }
}g;
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    f.cons(1,1,n);
    g.cons(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int t,l,r,s,c;
        cin>>t;
        if(t==1)
        {
            cin>>l>>r>>s>>c;
            g.update(1,1,n,l,l,s);
            if(r<n) g.update(1,1,n,r+1,r+1,-(s+c*(r-l)));
            g.update(1,1,n,l+1,r,c);
            f.updateadd(1,1,n,l,r,s-l*c);
            f.updatemul(1,1,n,l,r,c);
            if(n<=1000)
            {
                for(int j=l;j<=r;j++)
                {
                    a[j]+=s+(j-l)*c;
                }
            }
        }
        else if(t==2)
        {
            cin>>l>>r>>s>>c;
            int xx;
            if(l>1)
            {
                xx=f.get(1,1,n,l-1);
                if(n<=1000) xx=a[l-1];
                g.rupdate(1,1,n,l,l,s-xx);
            }
            if(r<n)
            {
                xx=f.get(1,1,n,r+1);
                if(n<=1000) xx=a[r+1];
                g.rupdate(1,1,n,r+1,r+1,xx-(s+(r-l)*c));
            }
            g.rupdate(1,1,n,l+1,r,c);
            f.updateset(1,1,n,l,r,s-l*c);
            f.updatemul(1,1,n,l,r,c);
            if(n<=1000)
            {
                for(int j=l;j<=r;j++)
                {
                    a[j]=s+(j-l)*c;
                }
            }
        }
        else
        {
            cin>>l>>r;
            if(l==r) cout<<1<<"\n";
            else
            {
                node siu=g.get(1,1,n,l+1,r);
                cout<<siu.opt.sc+1<<"\n";
            }

        }
    }

}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:227:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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