oj.uz

Submission #901384

# Submission time Handle Problem Language Result Execution time Memory
901384 2024-01-09T11:24:49 Z 12345678 Progression (NOI20_progression) C++17
35 / 100
 619 ms 129364 KB 
#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+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<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(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);
        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
*/

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 128596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 123612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 125776 KB Output is correct
2 Correct 108 ms 124244 KB Output is correct
3 Correct 107 ms 124144 KB Output is correct
4 Correct 105 ms 124276 KB Output is correct
5 Correct 107 ms 124252 KB Output is correct
6 Correct 106 ms 124240 KB Output is correct
7 Correct 110 ms 124176 KB Output is correct
8 Correct 17 ms 123992 KB Output is correct
9 Correct 17 ms 123704 KB Output is correct
10 Correct 17 ms 123740 KB Output is correct
11 Correct 394 ms 125624 KB Output is correct
12 Correct 349 ms 125948 KB Output is correct
13 Correct 406 ms 125480 KB Output is correct
14 Correct 415 ms 125688 KB Output is correct
15 Correct 349 ms 125916 KB Output is correct
16 Correct 405 ms 126044 KB Output is correct
17 Correct 410 ms 126352 KB Output is correct
18 Correct 396 ms 126196 KB Output is correct
19 Correct 376 ms 125524 KB Output is correct
20 Correct 358 ms 125608 KB Output is correct
21 Correct 372 ms 126060 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 126156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 125776 KB Output is correct
2 Correct 108 ms 124244 KB Output is correct
3 Correct 107 ms 124144 KB Output is correct
4 Correct 105 ms 124276 KB Output is correct
5 Correct 107 ms 124252 KB Output is correct
6 Correct 106 ms 124240 KB Output is correct
7 Correct 110 ms 124176 KB Output is correct
8 Correct 17 ms 123992 KB Output is correct
9 Correct 17 ms 123704 KB Output is correct
10 Correct 17 ms 123740 KB Output is correct
11 Correct 394 ms 125624 KB Output is correct
12 Correct 349 ms 125948 KB Output is correct
13 Correct 406 ms 125480 KB Output is correct
14 Correct 415 ms 125688 KB Output is correct
15 Correct 349 ms 125916 KB Output is correct
16 Correct 405 ms 126044 KB Output is correct
17 Correct 410 ms 126352 KB Output is correct
18 Correct 396 ms 126196 KB Output is correct
19 Correct 376 ms 125524 KB Output is correct
20 Correct 358 ms 125608 KB Output is correct
21 Correct 372 ms 126060 KB Output is correct
22 Incorrect 619 ms 129364 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 128596 KB Output isn't correct
2 Halted 0 ms 0 KB -