Submission #901398

#	Time	Username	Problem	Language	Result	Execution time	Memory
901398		12345678	Progression (NOI20_progression)	C++17	48 / 100	709 ms	134316 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

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;
        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) {}
        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 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)
    {
        d[i].push();
        if (l==r) return d[i].lzs=d[i].lzc=0, void();
        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=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 update1(int l, int r, int i, int ql, int qr, ll s, ll c)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lzs=s, d[i].lzc=c, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update1(l, md, 2*i, ql, qr, s, c);
        update1(md+1, r, 2*i+1, ql, qr, s+(md-l+1)*c, c);
        d[i]=d[2*i]+d[2*i+1];
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        cout<<"node "<<l<<' '<<r<<'\n';
        cout<<"max "<<d[i].mx<<' '<<d[i].mxl<<' '<<d[i].mxr<<'\n';
        cout<<"value "<<d[i].vl<<' '<<d[i].vr<<'\n';
        cout<<"gapl "<<d[i].gapl.type<<' '<<d[i].gapl.g<<'\n';
        cout<<"gapr "<<d[i].gapr.type<<' '<<d[i].gapr.g<<'\n';
        cout<<"sz "<<d[i].sz<<'\n';
        cout<<"lz "<<d[i].lzs<<' '<<d[i].lzc<<'\n';
        cout<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
    void show2(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) return void(cout<<d[i].vl<<' ');
        int md=(l+r)/2;
        show2(l, md, 2*i);
        show2(md+1, r, 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);
    //s.show(1, n, 1);
    while (q--)
    {
        cin>>t;
        if (t==1) cin>>l>>r>>ss>>c, s.update1(1, n, 1, l, r, ss-c*(l-1), c); //s.show2(1, n, 1), cout<<'\n';
        if (t==2) continue;
        if (t==3) cin>>l>>r, cout<<s.query(1, n, 1, l, r).mx<<'\n';
    }
}

/*
0 0 0 0 1 2 3 4 5 5

10 4
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10

5 10
2 4 6 4 2
3 1 1
3 1 2
3 1 3
3 1 4
3 1 5
3 2 2
3 2 3
3 2 4
3 2 5
3 3 3

5 5
1 2 5 3 4
1 1 2 3 -3    4 2 
1 1 5 1 1
1 5 5 10 2
1 3 5 4 -3
1 1 1 1 1

5 1
1 2 5 3 4
1 1 2 3 -3
*/

Compilation message (stderr)

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

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