Submission #901329

#	Time	Username	Problem	Language	Result	Execution time	Memory
901329		12345678	Progression (NOI20_progression)	C++17	0 / 100	234 ms	113144 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;

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;
        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) {}
        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(res.mx, res.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;
        }
    } d[4*nx];
    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];
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        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) continue;
        if (t==2) continue;
        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:24:36: warning: 'segtree::node::vr' will be initialized after [-Wreorder]
   24 |         ll type, mx, mxl, mxr, vl, vr, sz;
      |                                    ^~
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) {}
      |         ^~~~

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