oj.uz

Submission #901410

# Submission time Handle Problem Language Result Execution time Memory
901410 2024-01-09T11:57:56 Z 12345678 Progression (NOI20_progression) C++17
100 / 100
 921 ms 163744 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, 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];
    }
    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<<' '<<d[i].lzss<<' '<<d[i].lzsc<<' '<<d[i].isset<<'\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.update(1, n, 1, l, r, ss-c*(l-1), c, 0); //s.show2(1, n, 1), cout<<'\n';
        if (t==2) cin>>l>>r>>ss>>c, s.update(1, n, 1, l, r, ss-c*(l-1), c, 1); //s.show(1, n, 1), cout<<'\n';
        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
2 1 2 3 -3
2 1 5 1 1
2 5 5 10 2
2 3 5 4 -3
2 1 1 1 1

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

0 0 0 0 -2 -4 -6 -8 -10 -12
*/

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, lzss, lzsc, isset;
      |                                    ^~
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), lzss(0), lzsc(0), isset(0){}
      |         ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 153884 KB Output is correct
2 Correct 97 ms 155472 KB Output is correct
3 Correct 101 ms 155636 KB Output is correct
4 Correct 83 ms 155580 KB Output is correct
5 Correct 84 ms 155728 KB Output is correct
6 Correct 85 ms 155728 KB Output is correct
7 Correct 91 ms 155648 KB Output is correct
8 Correct 22 ms 152268 KB Output is correct
9 Correct 22 ms 152404 KB Output is correct
10 Correct 21 ms 152412 KB Output is correct
11 Correct 129 ms 161532 KB Output is correct
12 Correct 131 ms 161652 KB Output is correct
13 Correct 130 ms 161876 KB Output is correct
14 Correct 132 ms 161872 KB Output is correct
15 Correct 131 ms 161872 KB Output is correct
16 Correct 165 ms 161552 KB Output is correct
17 Correct 130 ms 161388 KB Output is correct
18 Correct 130 ms 161404 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 152412 KB Output is correct
2 Correct 22 ms 152408 KB Output is correct
3 Correct 21 ms 152408 KB Output is correct
4 Correct 21 ms 152412 KB Output is correct
5 Correct 21 ms 152408 KB Output is correct
6 Correct 21 ms 152412 KB Output is correct
7 Correct 22 ms 152404 KB Output is correct
8 Correct 22 ms 152400 KB Output is correct
9 Correct 22 ms 152404 KB Output is correct
10 Correct 22 ms 152412 KB Output is correct
11 Correct 22 ms 152416 KB Output is correct
12 Correct 22 ms 152412 KB Output is correct
13 Correct 23 ms 152396 KB Output is correct
14 Correct 22 ms 152416 KB Output is correct
15 Correct 23 ms 152404 KB Output is correct
16 Correct 22 ms 152412 KB Output is correct
17 Correct 22 ms 152360 KB Output is correct
18 Correct 24 ms 152400 KB Output is correct
19 Correct 22 ms 152400 KB Output is correct
20 Correct 22 ms 152400 KB Output is correct
21 Correct 21 ms 152328 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 154108 KB Output is correct
2 Correct 116 ms 152916 KB Output is correct
3 Correct 142 ms 152852 KB Output is correct
4 Correct 113 ms 152912 KB Output is correct
5 Correct 117 ms 153088 KB Output is correct
6 Correct 122 ms 153128 KB Output is correct
7 Correct 116 ms 153048 KB Output is correct
8 Correct 20 ms 152412 KB Output is correct
9 Correct 21 ms 152272 KB Output is correct
10 Correct 22 ms 152412 KB Output is correct
11 Correct 480 ms 154172 KB Output is correct
12 Correct 393 ms 153984 KB Output is correct
13 Correct 484 ms 153868 KB Output is correct
14 Correct 486 ms 153944 KB Output is correct
15 Correct 385 ms 153888 KB Output is correct
16 Correct 496 ms 154252 KB Output is correct
17 Correct 482 ms 154656 KB Output is correct
18 Correct 473 ms 154360 KB Output is correct
19 Correct 460 ms 153556 KB Output is correct
20 Correct 425 ms 153688 KB Output is correct
21 Correct 433 ms 153612 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 157408 KB Output is correct
2 Correct 172 ms 155588 KB Output is correct
3 Correct 141 ms 155680 KB Output is correct
4 Correct 140 ms 155552 KB Output is correct
5 Correct 142 ms 155732 KB Output is correct
6 Correct 144 ms 155728 KB Output is correct
7 Correct 152 ms 155800 KB Output is correct
8 Correct 21 ms 152400 KB Output is correct
9 Correct 23 ms 152232 KB Output is correct
10 Correct 22 ms 152408 KB Output is correct
11 Correct 569 ms 159624 KB Output is correct
12 Correct 562 ms 162896 KB Output is correct
13 Correct 567 ms 159512 KB Output is correct
14 Correct 563 ms 159880 KB Output is correct
15 Correct 516 ms 163128 KB Output is correct
16 Correct 620 ms 162880 KB Output is correct
17 Correct 629 ms 162844 KB Output is correct
18 Correct 585 ms 163068 KB Output is correct
19 Correct 565 ms 162748 KB Output is correct
20 Correct 543 ms 162788 KB Output is correct
21 Correct 567 ms 162896 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 154108 KB Output is correct
2 Correct 116 ms 152916 KB Output is correct
3 Correct 142 ms 152852 KB Output is correct
4 Correct 113 ms 152912 KB Output is correct
5 Correct 117 ms 153088 KB Output is correct
6 Correct 122 ms 153128 KB Output is correct
7 Correct 116 ms 153048 KB Output is correct
8 Correct 20 ms 152412 KB Output is correct
9 Correct 21 ms 152272 KB Output is correct
10 Correct 22 ms 152412 KB Output is correct
11 Correct 480 ms 154172 KB Output is correct
12 Correct 393 ms 153984 KB Output is correct
13 Correct 484 ms 153868 KB Output is correct
14 Correct 486 ms 153944 KB Output is correct
15 Correct 385 ms 153888 KB Output is correct
16 Correct 496 ms 154252 KB Output is correct
17 Correct 482 ms 154656 KB Output is correct
18 Correct 473 ms 154360 KB Output is correct
19 Correct 460 ms 153556 KB Output is correct
20 Correct 425 ms 153688 KB Output is correct
21 Correct 433 ms 153612 KB Output is correct
22 Correct 774 ms 153408 KB Output is correct
23 Correct 151 ms 152912 KB Output is correct
24 Correct 147 ms 152732 KB Output is correct
25 Correct 145 ms 152656 KB Output is correct
26 Correct 147 ms 152552 KB Output is correct
27 Correct 150 ms 152948 KB Output is correct
28 Correct 148 ms 152652 KB Output is correct
29 Correct 22 ms 152412 KB Output is correct
30 Correct 21 ms 152412 KB Output is correct
31 Correct 21 ms 152412 KB Output is correct
32 Correct 791 ms 153616 KB Output is correct
33 Correct 723 ms 153216 KB Output is correct
34 Correct 780 ms 154200 KB Output is correct
35 Correct 786 ms 153692 KB Output is correct
36 Correct 723 ms 153960 KB Output is correct
37 Correct 710 ms 153712 KB Output is correct
38 Correct 708 ms 153740 KB Output is correct
39 Correct 727 ms 153672 KB Output is correct
40 Correct 776 ms 153948 KB Output is correct
41 Correct 808 ms 153428 KB Output is correct
42 Correct 755 ms 153424 KB Output is correct
43 Correct 732 ms 153428 KB Output is correct
44 Correct 707 ms 153424 KB Output is correct
45 Correct 713 ms 153548 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 153884 KB Output is correct
2 Correct 97 ms 155472 KB Output is correct
3 Correct 101 ms 155636 KB Output is correct
4 Correct 83 ms 155580 KB Output is correct
5 Correct 84 ms 155728 KB Output is correct
6 Correct 85 ms 155728 KB Output is correct
7 Correct 91 ms 155648 KB Output is correct
8 Correct 22 ms 152268 KB Output is correct
9 Correct 22 ms 152404 KB Output is correct
10 Correct 21 ms 152412 KB Output is correct
11 Correct 129 ms 161532 KB Output is correct
12 Correct 131 ms 161652 KB Output is correct
13 Correct 130 ms 161876 KB Output is correct
14 Correct 132 ms 161872 KB Output is correct
15 Correct 131 ms 161872 KB Output is correct
16 Correct 165 ms 161552 KB Output is correct
17 Correct 130 ms 161388 KB Output is correct
18 Correct 130 ms 161404 KB Output is correct
19 Correct 29 ms 152412 KB Output is correct
20 Correct 22 ms 152408 KB Output is correct
21 Correct 21 ms 152408 KB Output is correct
22 Correct 21 ms 152412 KB Output is correct
23 Correct 21 ms 152408 KB Output is correct
24 Correct 21 ms 152412 KB Output is correct
25 Correct 22 ms 152404 KB Output is correct
26 Correct 22 ms 152400 KB Output is correct
27 Correct 22 ms 152404 KB Output is correct
28 Correct 22 ms 152412 KB Output is correct
29 Correct 22 ms 152416 KB Output is correct
30 Correct 22 ms 152412 KB Output is correct
31 Correct 23 ms 152396 KB Output is correct
32 Correct 22 ms 152416 KB Output is correct
33 Correct 23 ms 152404 KB Output is correct
34 Correct 22 ms 152412 KB Output is correct
35 Correct 22 ms 152360 KB Output is correct
36 Correct 24 ms 152400 KB Output is correct
37 Correct 22 ms 152400 KB Output is correct
38 Correct 22 ms 152400 KB Output is correct
39 Correct 21 ms 152328 KB Output is correct
40 Correct 436 ms 154108 KB Output is correct
41 Correct 116 ms 152916 KB Output is correct
42 Correct 142 ms 152852 KB Output is correct
43 Correct 113 ms 152912 KB Output is correct
44 Correct 117 ms 153088 KB Output is correct
45 Correct 122 ms 153128 KB Output is correct
46 Correct 116 ms 153048 KB Output is correct
47 Correct 20 ms 152412 KB Output is correct
48 Correct 21 ms 152272 KB Output is correct
49 Correct 22 ms 152412 KB Output is correct
50 Correct 480 ms 154172 KB Output is correct
51 Correct 393 ms 153984 KB Output is correct
52 Correct 484 ms 153868 KB Output is correct
53 Correct 486 ms 153944 KB Output is correct
54 Correct 385 ms 153888 KB Output is correct
55 Correct 496 ms 154252 KB Output is correct
56 Correct 482 ms 154656 KB Output is correct
57 Correct 473 ms 154360 KB Output is correct
58 Correct 460 ms 153556 KB Output is correct
59 Correct 425 ms 153688 KB Output is correct
60 Correct 433 ms 153612 KB Output is correct
61 Correct 589 ms 157408 KB Output is correct
62 Correct 172 ms 155588 KB Output is correct
63 Correct 141 ms 155680 KB Output is correct
64 Correct 140 ms 155552 KB Output is correct
65 Correct 142 ms 155732 KB Output is correct
66 Correct 144 ms 155728 KB Output is correct
67 Correct 152 ms 155800 KB Output is correct
68 Correct 21 ms 152400 KB Output is correct
69 Correct 23 ms 152232 KB Output is correct
70 Correct 22 ms 152408 KB Output is correct
71 Correct 569 ms 159624 KB Output is correct
72 Correct 562 ms 162896 KB Output is correct
73 Correct 567 ms 159512 KB Output is correct
74 Correct 563 ms 159880 KB Output is correct
75 Correct 516 ms 163128 KB Output is correct
76 Correct 620 ms 162880 KB Output is correct
77 Correct 629 ms 162844 KB Output is correct
78 Correct 585 ms 163068 KB Output is correct
79 Correct 565 ms 162748 KB Output is correct
80 Correct 543 ms 162788 KB Output is correct
81 Correct 567 ms 162896 KB Output is correct
82 Correct 774 ms 153408 KB Output is correct
83 Correct 151 ms 152912 KB Output is correct
84 Correct 147 ms 152732 KB Output is correct
85 Correct 145 ms 152656 KB Output is correct
86 Correct 147 ms 152552 KB Output is correct
87 Correct 150 ms 152948 KB Output is correct
88 Correct 148 ms 152652 KB Output is correct
89 Correct 22 ms 152412 KB Output is correct
90 Correct 21 ms 152412 KB Output is correct
91 Correct 21 ms 152412 KB Output is correct
92 Correct 791 ms 153616 KB Output is correct
93 Correct 723 ms 153216 KB Output is correct
94 Correct 780 ms 154200 KB Output is correct
95 Correct 786 ms 153692 KB Output is correct
96 Correct 723 ms 153960 KB Output is correct
97 Correct 710 ms 153712 KB Output is correct
98 Correct 708 ms 153740 KB Output is correct
99 Correct 727 ms 153672 KB Output is correct
100 Correct 776 ms 153948 KB Output is correct
101 Correct 808 ms 153428 KB Output is correct
102 Correct 755 ms 153424 KB Output is correct
103 Correct 732 ms 153428 KB Output is correct
104 Correct 707 ms 153424 KB Output is correct
105 Correct 713 ms 153548 KB Output is correct
106 Correct 921 ms 163348 KB Output is correct
107 Correct 179 ms 155904 KB Output is correct
108 Correct 167 ms 155728 KB Output is correct
109 Correct 171 ms 155728 KB Output is correct
110 Correct 20 ms 152400 KB Output is correct
111 Correct 22 ms 152408 KB Output is correct
112 Correct 21 ms 152404 KB Output is correct
113 Correct 765 ms 162744 KB Output is correct
114 Correct 804 ms 162720 KB Output is correct
115 Correct 769 ms 162420 KB Output is correct
116 Correct 723 ms 162356 KB Output is correct
117 Correct 894 ms 163348 KB Output is correct
118 Correct 737 ms 162388 KB Output is correct
119 Correct 736 ms 162392 KB Output is correct
120 Correct 483 ms 161168 KB Output is correct
121 Correct 485 ms 160840 KB Output is correct
122 Correct 497 ms 160848 KB Output is correct
123 Correct 440 ms 160256 KB Output is correct
124 Correct 443 ms 160104 KB Output is correct
125 Correct 425 ms 159992 KB Output is correct
126 Correct 884 ms 159956 KB Output is correct
127 Correct 886 ms 159800 KB Output is correct
128 Correct 893 ms 163460 KB Output is correct
129 Correct 891 ms 160048 KB Output is correct
130 Correct 819 ms 160004 KB Output is correct
131 Correct 795 ms 159876 KB Output is correct
132 Correct 791 ms 160092 KB Output is correct
133 Correct 903 ms 163744 KB Output is correct
134 Correct 905 ms 163420 KB Output is correct
135 Correct 899 ms 163416 KB Output is correct
136 Correct 176 ms 155732 KB Output is correct
137 Correct 168 ms 155656 KB Output is correct
138 Correct 170 ms 155696 KB Output is correct