Submission #1178114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178114		vnedu	Progression (NOI20_progression)	C++20	100 / 100	762 ms	112248 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 3e5 + 35;
const int Q = 3e5 + 35;
const ll inf = LLONG_MAX;

int n,q;
ll a[N],d[N];
pair<ll,ll> laz[N<<2],realpart[N<<2],imagpart[N<<2];

struct node
{
    int mx,l,r;
    pair<int,ll> pre,suf;
    node(){mx=0;pre.fi=-1;}
    void print()
    {
        cout<<mx<<' '<<l<<' '<<r<<' '<<pre.fi<<' '<<pre.se<<' '<<suf.fi<<' '<<suf.se<<'\n';
    }
    void init(ll x)
    {
        mx=r-l+1;
        pre=make_pair(r-l+1,x);
        suf=make_pair(r-l+1,x);
    }

    node getCopy()
    {
        return *this;
    }

    node operator * (const node &S)
    {
        if (pre.fi==-1) return S;
        if (S.pre.fi==-1) return getCopy();
        node ans; ans.l=l,ans.r=S.r;
        ans.mx=max(mx,S.mx);
        ans.pre=pre;
        if (pre.fi==r-l+1 && S.pre.se==pre.se) ans.pre.fi+=S.pre.fi;
        ans.suf=S.suf;
        if (S.suf.fi==S.r-S.l+1 && S.suf.se==suf.se) ans.suf.fi+=suf.fi;
        if (suf.se==S.pre.se) maximize(ans.mx,suf.fi+S.pre.fi);
//        cout<<l<<' '<<r<<' '<<S.l<<' '<<S.r<<'\n';
        return ans;
    }
} t[N<<2];

void push(int id)
{
    pair<ll,ll> &cur=laz[id];
    if (cur.fi!=inf)
    {
        t[id<<1].init(cur.fi); t[id<<1|1].init(cur.fi);
        laz[id<<1]=laz[id<<1|1]=make_pair(cur.fi,0);
        cur.fi=inf;
    }
    if (cur.se!=0)
    {
        t[id<<1].pre.se+=cur.se;
        t[id<<1].suf.se+=cur.se;
        t[id<<1|1].pre.se+=cur.se;
        t[id<<1|1].suf.se+=cur.se;
        laz[id<<1].se+=cur.se;
        laz[id<<1|1].se+=cur.se;
        cur.se=0;
    }
}
void traverse(int id, int l, int r)
{
    if (l!=1)
    {
        cout<<l<<' '<<r<<'\n';
        t[id].print();
    }
    if (l==r) return;
    int mid((l+r)>>1);
    push(id);
    traverse(id<<1,l,mid);
    traverse(id<<1|1,mid+1,r);
}

void build(int id, int l, int r)
{
    node &cur=t[id];
    cur.l=l,cur.r=r;
    laz[id]=imagpart[id]=realpart[id]=make_pair(inf,0);
    if (l==r)
    {
        cur.init(d[l]);
//        cout<<l<<' '<<r<<'\n';
//        cur.print();
        return;
    }
    int mid((l+r)>>1);
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
//    cout<<l<<' '<<r<<'\n';
    t[id]=t[id<<1]*t[id<<1|1];
//    t[id].print();
//    cout<<l<<' '<<r<<' '<<t[id].l<<' '<<t[id].r<<'\n';
}
void add(int id, int l, int r, int u, int v, ll val)
{
    if (l>v||r<u) return;
    if (u<=l && r<=v)
    {
        t[id].pre.se+=val;
        t[id].suf.se+=val;
        laz[id].se+=val;
//        cout<<laz[id].fi<<' '<<laz[id].se<<'\n';
//        push(id);
//        t[id<<1].print();
        return;
    }
    push(id);
    int mid((l+r)>>1);
    add(id<<1,l,mid,u,v,val);
    add(id<<1|1,mid+1,r,u,v,val);
    t[id]=t[id<<1]*t[id<<1|1];
}
void update(int id, int l, int r, int u, int v, ll val)
{
    if (l>v||r<u) return;
    if (u<=l && r<=v)
    {
        t[id].init(val);
        laz[id]=make_pair(val,0);
        return;
    }
    push(id);
    int mid((l+r)>>1);
    update(id<<1,l,mid,u,v,val);
    update(id<<1|1,mid+1,r,u,v,val);
    t[id]=t[id<<1]*t[id<<1|1];
}
node get(int id, int l, int r, int u, int v)
{
    if (l>v||r<u) return node();
    if (u<=l && r<=v) return t[id];
    push(id);
    int mid((l+r)>>1);
    return get(id<<1,l,mid,u,v)*get(id<<1|1,mid+1,r,u,v);
}
void pushpos(int id)
{
    if (realpart[id].fi!=inf)
    {
        realpart[id<<1]=realpart[id<<1|1]=make_pair(realpart[id].fi,0);
        realpart[id].fi=inf;
    }
    if (realpart[id].se!=0)
    {
        realpart[id<<1].se+=realpart[id].se;
        realpart[id<<1|1].se+=realpart[id].se;
        realpart[id].se=0;
    }
    if (imagpart[id].fi!=inf)
    {
        imagpart[id<<1]=imagpart[id<<1|1]=make_pair(imagpart[id].fi,0);
        imagpart[id].fi=inf;
    }
    if (imagpart[id].se!=0)
    {
        imagpart[id<<1].se+=imagpart[id].se;
        imagpart[id<<1|1].se+=imagpart[id].se;
        imagpart[id].se=0;
    }
}
void addpos(int id, int l, int r, int u, int v, ll R, ll i)
{
    if (l>v||r<u) return;
    if (u<=l && r<=v)
    {
        realpart[id].se+=R;
        imagpart[id].se+=i;
        return;
    }
    pushpos(id);
    int mid((l+r)>>1);
    addpos(id<<1,l,mid,u,v,R,i);
    addpos(id<<1|1,mid+1,r,u,v,R,i);
}
void updatepos(int id, int l, int r, int u, int v, ll R, ll i)
{
    if (l>v||r<u) return;
    if (u<=l && r<=v)
    {
        realpart[id]=make_pair(R,0);
        imagpart[id]=make_pair(i,0);
        return;
    }
    pushpos(id);
    int mid((l+r)>>1);
    updatepos(id<<1,l,mid,u,v,R,i);
    updatepos(id<<1|1,mid+1,r,u,v,R,i);
}
ll getpos(int pos)
{
    int id=1,l=1,r=n,mid;
    while (l<r)
    {
        mid=(l+r)>>1;
        pushpos(id);
        if (pos<=mid) r=mid,id=(id<<1);
        else l=mid+1,id=(id<<1|1);
    }
    ll ans=0;
    ans+=(realpart[id].fi==inf?a[pos]:realpart[id].fi)+realpart[id].se;
    ans+=pos*((imagpart[id].fi==inf?0:imagpart[id].fi)+imagpart[id].se);
    return ans;
}

void solve()
{
    cin>>n>>q;
    for (int i=1; i<=n; ++i) cin>>a[i];
    for (int i=2; i<=n; ++i) d[i]=a[i]-a[i-1];
//    for (int i=1; i<=n; ++i) cout<<d[i]<<' ';
//    cout<<'\n';
    build(1,1,n);
//    traverse(1,1,n);
//    return;
//    return;
//    cout<<'\n';
//    for (int i=1; i<=n; ++i) cout<<getpos(i)<<' ';
//    cout<<'\n';
//    return;
    while (q--)
    {
        int type; cin>>type;
        if (type==1)
        {
            int l,r,s,c; cin>>l>>r>>s>>c;
            if (l<r) add(1,1,n,l+1,r,c);
            if (l>1) add(1,1,n,l,l,s);
            if (r<n) add(1,1,n,r+1,r+1,-(s+(r-l)*1LL*c));
            addpos(1,1,n,l,r,s-l*1LL*c,c);
        }
        else if (type==2)
        {
            int l,r,s,c; cin>>l>>r>>s>>c;
            if (l<r) update(1,1,n,l+1,r,c);
//            cout<<laz[3].fi<<' '<<laz[3].se<<'\n';
            if (l>1)
            {
                ll cur=getpos(l-1);
                update(1,1,n,l,l,s-cur);
            }
            if (r<n)
            {
                ll cur=getpos(r+1);
                update(1,1,n,r+1,r+1,cur-(s+(r-l)*1LL*c));
            }
            updatepos(1,1,n,l,r,s-l*1LL*c,c);
        }
        else
        {
            int l,r; cin>>l>>r;
            if (l==r) cout<<1<<'\n';
            else cout<<get(1,1,n,l+1,r).mx+1<<'\n';
        }
    }
//    traverse(1,1,n);
//    cout<<'\n';
//    for (int i=2; i<=n; ++i) cout<<getpos(i)-getpos(i-1)<<' ';
//    cout<<'\n';
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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