Submission #901411

#	Time	Username	Problem	Language	Result	Execution time	Memory
901411		12345678	Progression (NOI20_progression)	C++17	100 / 100	1049 ms	154652 KiB

Progression

#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=3e5+5;
#define ll long long

ll n, q, v[nx], t, l, r, ss, c;

struct gap
{
    ll type, g;
    gap(ll type=0, ll g=0): type(type), g(g){}
    friend bool operator==(const gap &lhs, const gap &rhs) {return lhs.type||rhs.type||lhs.g==rhs.g;}
    friend bool operator!=(const gap &lhs, const gap &rhs) {return !(lhs==rhs);}
};
gap opposite(gap o) { return gap(o.type, -o.g);}

struct segtree
{
    struct node
    {
        gap gapl, gapr;
        ll type, mx, mxl, mxr, vl, vr, sz, lzs, lzc, lzss, lzsc, isset;
        node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1), lzs(0), lzc(0), lzss(0), lzsc(0), isset(0){}
        friend node operator+(const node &lhs, const node &rhs)
        {
            if (lhs.type) return rhs;
            if (rhs.type) return lhs;
            node res=node();
            gap gapl=gap(0, rhs.vl-lhs.vr), gapr=gap(0, lhs.vr-rhs.vl);
            res.vl=lhs.vl;
            res.vr=rhs.vr;
            res.sz=lhs.sz+rhs.sz;
            res.gapl=lhs.gapl.type?gapl:lhs.gapl;
            res.gapr=rhs.gapr.type?gapr:rhs.gapr;
            if (lhs.mxl!=lhs.sz||lhs.gapl!=gapl) res.mxl=lhs.mxl;
            else res.mxl=(gapl==rhs.gapl)?lhs.mxl+rhs.mxl:lhs.mxl+1;
            if (rhs.mxr!=rhs.sz||rhs.gapr!=gapr) res.mxr=rhs.mxr;
            else res.mxr=(gapr==lhs.gapr)?lhs.mxr+rhs.mxr:rhs.mxr+1;
            res.mx=max(lhs.mx, rhs.mx);
            if (opposite(lhs.gapr)==gapl) res.mx=max(res.mx, lhs.mxr+1);
            if (rhs.gapl==gapl) res.mx=max(res.mx, rhs.mxl+1);
            if (opposite(lhs.gapr)==gapl&&gapl==rhs.gapl) res.mx=max(res.mx, lhs.mxr+rhs.mxl);
            return res;
        }
        void set()
        {
            vl=lzss;
            vr=lzss+(sz-1)*lzsc;
            gapl=(sz!=1)?gap(0, lzsc):gap(1);
            gapr=(sz!=1)?gap(0, -lzsc):gap(1);
            mx=mxl=mxr=sz;
        }
        void push()
        {
            vl+=lzs;
            vr+=lzs+lzc*(sz-1);
            gapl.g+=lzc;
            gapr.g-=lzc;
        }
    } d[4*nx];
    void pushlz(int l, int r, int i)
    {
        if (d[i].isset) d[i].set();
        d[i].push();
        if (l==r) return d[i].lzs=d[i].lzc=d[i].lzss=d[i].lzsc=d[i].isset=0, void();
        if (d[i].isset) 
        {
            d[2*i].lzs=d[2*i].lzc=d[2*i+1].lzs=d[2*i+1].lzc=0;
            d[2*i].lzss=d[i].lzss;
            d[2*i+1].lzss=d[i].lzss+d[2*i].sz*d[i].lzsc;
            d[2*i].lzsc=d[2*i+1].lzsc=d[i].lzsc;
            d[2*i].isset=d[2*i+1].isset=1;
        }
        d[2*i].lzs+=d[i].lzs;
        d[2*i].lzc+=d[i].lzc;
        d[2*i+1].lzs+=d[i].lzs+d[2*i].sz*d[i].lzc;
        d[2*i+1].lzc+=d[i].lzc;
        d[i].lzs=d[i].lzc=d[i].lzss=d[i].lzsc=d[i].isset=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=node(v[l], 0));
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update(int l, int r, int i, int ql, int qr, ll s, ll c, bool type)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr&&!type) return d[i].lzs=s, d[i].lzc=c, pushlz(l, r, i), void();
        if (ql<=l&&r<=qr&&type) return d[i].lzss=s, d[i].lzsc=c, d[i].isset=1, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, s, c, type);
        update(md+1, r, 2*i+1, ql, qr, s+(md-l+1)*c, c, type);
        d[i]=d[2*i]+d[2*i+1];
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return node(0, 1);
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>v[i];
    s.build(1, n, 1);
    while (q--)
    {
        cin>>t;
        if (t==1) cin>>l>>r>>ss>>c, s.update(1, n, 1, l, r, ss-c*(l-1), c, 0);
        if (t==2) cin>>l>>r>>ss>>c, s.update(1, n, 1, l, r, ss-c*(l-1), c, 1);
        if (t==3) cin>>l>>r, cout<<s.query(1, n, 1, l, r).mx<<'\n';
    }
}

Compilation message (stderr)

Progression.cpp: In constructor 'segtree::node::node(long long int, long long int)':
Progression.cpp:26:36: warning: 'segtree::node::vr' will be initialized after [-Wreorder]
   26 |         ll type, mx, mxl, mxr, vl, vr, sz, lzs, lzc, lzss, lzsc, isset;
      |                                    ^~
Progression.cpp:25:13: warning:   'gap segtree::node::gapl' [-Wreorder]
   25 |         gap gapl, gapr;
      |             ^~~~
Progression.cpp:27:9: warning:   when initialized here [-Wreorder]
   27 |         node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1), lzs(0), lzc(0), lzss(0), lzsc(0), isset(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