oj.uz

Submission #736552

# Submission time Handle Problem Language Result Execution time Memory
736552 2023-05-05T23:38:31 Z Ronin13 Progression (NOI20_progression) C++14
68 / 100
 1070 ms 153752 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int nmax = 500001;

struct node{
    ll x, y;
    ll pr, suf;
    ll sum, lazy, lazy1;
    bool good = false;
    ll ans = 0;
    node(){
        x = y = 0;
        pr = suf = 0;
        sum = lazy1 = 0;
        lazy = -1e18;
        ans = 0;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.pr = a.pr;
    c.suf = b.suf;
    c.x = a.x;
    c.y = b.y;
    if(a.good){
        if(b.x == a.x) c.pr += b.pr;
    }
    if(b.good){
        if(a.y == b.y) c.suf += a.suf;
    }
    if(a.good && b.good && a.x == b.x)
        c.good = true;
    c.ans = max(a.ans, b.ans);
    if(a.y == b.x){
        c.ans = max(c.ans, a.suf + b.pr);
    }
    return c;
}
//lazy minichebis lazy1 damatebis
void push1(int v, int l, int r){
    if(t[v].lazy == -1e18)return;
    t[v * 2].lazy = t[v].lazy;
    t[v * 2].lazy1 = -1e18;
    t[v * 2 + 1].lazy = t[v].lazy;
    t[v * 2 + 1].lazy1 = -1e18;
    int m = (l + r) /2;
    t[v * 2].sum = (ll)(m - l + 1) * t[v].lazy;
    t[v * 2 + 1].sum = (ll)(r - m) * t[v].lazy;
    t[v * 2].good = true;
    t[v * 2].pr = t[v * 2].suf = m - l + 1;
    t[v * 2].x = t[v * 2].y = t[v].lazy;
    t[v * 2 + 1].good = true;
    t[v * 2 + 1].pr = t[v * 2 + 1].suf = r - m;
    t[v * 2 + 1].x = t[v * 2 + 1].y = t[v].lazy;
    t[v].lazy = -1e18;
}

void push2(int v, int l, int r){
    if(t[v].lazy1 == 0) return;
    ll m = (l + r) / 2;
    if(t[v * 2].lazy != -1e18) t[v * 2].lazy += t[v].lazy1;
    if(t[v * 2 + 1].lazy != -1e18) t[v * 2 + 1].lazy += t[v].lazy1;
    t[v * 2].lazy1 += t[v].lazy1;
    t[v * 2 + 1].lazy1 += t[v].lazy1;
    t[v * 2].x += t[v].lazy1;
    t[v * 2].y += t[v].lazy1;
    t[v * 2 + 1].x += t[v].lazy1;
    t[v * 2 + 1].y += t[v].lazy1;
    t[v * 2].sum += t[v].lazy1 * (ll)(m - l + 1);
    t[v * 2 + 1].sum += t[v].lazy1 * (ll)(r - m);
    t[v].lazy1 = 0;
}

void updran1(int v, int l, int r, int st, int fin, ll val){//minicheba intervalze
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v].sum = val * (ll)(r - l + 1);
        t[v].x = t[v].y = val;
        t[v].pr = t[v].suf = r - l + 1;
        t[v].lazy = val;
        t[v].lazy1 = 0;
        t[v].good = true;
        return;
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    updran1(2 * v, l, m, st, fin, val);
    updran1(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}


void updran2(int v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v].sum += val * (ll)(r - l + 1);
        t[v].x += val;
        t[v].y += val;
        if(t[v].lazy != -1e18) t[v].lazy += val;
        t[v].lazy1 += val;
        return;
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    updran2(2 * v, l, m, st, fin, val);
    updran2(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

void upd_p(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos){
        return;
    }
    if(l == r){
        t[v].sum = val;
        t[v].x = t[v].y = val;
        t[v].lazy = -1e18;
        t[v].lazy1 = 0;
        t[v].pr = t[v].suf = 1;
        t[v].ans = 1;
        t[v].good = true;
        return;
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    upd_p(2 * v, l, m, pos, val);
    upd_p(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

ll getsum(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin)
        return t[v].sum;
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    return getsum(2 * v, l, m,st, fin) + getsum(2 * v + 1, m + 1, r, st, fin);
}

node getans(int v, int l, int r, int tl, int tr){
    if(l == tl && r == tr){
        return t[v];
    }
    push1(v, l, r);
    push2(v, l, r);
    int m = (l + r) / 2;
    if(tl > m)
        return getans(2 * v + 1, m + 1, r, tl, tr);
    if(tr <= m)
        return getans(2 * v, l, m, tl, tr);
    return merg(getans(2 * v, l, m, tl, m), getans(2 * v + 1, m + 1, r, m + 1, tr));
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    ll a[n + 1];
    for(int i = 1; i<= n; ++i){
        cin >> a[i];
    }
    for(int i = 2; i <= n; i++){
        upd_p(1, 1, n, i - 1, a[i] - a[i - 1]);
    }
    while(q--){
        int t; cin >> t;
        if(t == 3){
            int l, r; cin >> l >> r;
            if(l == r) cout << 1 << "\n";
            else
            cout << getans(1, 1, n, l, r - 1).ans + 1 << "\n";
        }
        if(t == 1){
            ll l, r, s, c; cin >> l >> r >> s >> c;
            if(l > 1){
                ll x = getsum(1, 1, n, l - 1, l - 1);
                upd_p(1, 1, n, l - 1, s + x);
            }
            else a[1] += s;
            updran2(1,1, n, l, r - 1, c);
            ll val = s + c * (r - l);
            val = -val + getsum(1, 1, n, r, r);
            if(r != n)upd_p(1, 1, n, r, val);
        }
        if(t == 2){
            ll l, r, s, c; cin >> l >> r >> s >> c;
            ll x = getsum(1, 1, n, 1, l - 2) + a[1];
            ll y =  getsum(1, 1, n, 1, r) + a[1];
            if(l > 1){

                upd_p(1, 1, n, l - 1, s - x);
            }
            if(r < n){
                x = y;
                upd_p(1, 1, n, r, x - s - (r - l) * c);
            }
            if(l == 1){
                a[1] = s;
            }
            updran1(1, 1, n, l, r - 1, c);
        }
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 145816 KB Output is correct
2 Correct 169 ms 142944 KB Output is correct
3 Correct 173 ms 142992 KB Output is correct
4 Correct 169 ms 143164 KB Output is correct
5 Correct 174 ms 143148 KB Output is correct
6 Correct 190 ms 143180 KB Output is correct
7 Correct 166 ms 143132 KB Output is correct
8 Correct 55 ms 141132 KB Output is correct
9 Correct 59 ms 141120 KB Output is correct
10 Correct 68 ms 141132 KB Output is correct
11 Correct 511 ms 145828 KB Output is correct
12 Correct 516 ms 145704 KB Output is correct
13 Correct 507 ms 146116 KB Output is correct
14 Correct 502 ms 146104 KB Output is correct
15 Correct 512 ms 145988 KB Output is correct
16 Correct 508 ms 145760 KB Output is correct
17 Correct 517 ms 145736 KB Output is correct
18 Correct 506 ms 145788 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 141132 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 463 ms 146208 KB Output is correct
2 Correct 154 ms 143220 KB Output is correct
3 Correct 134 ms 143276 KB Output is correct
4 Correct 132 ms 143280 KB Output is correct
5 Correct 135 ms 143328 KB Output is correct
6 Correct 135 ms 143368 KB Output is correct
7 Correct 143 ms 143388 KB Output is correct
8 Correct 57 ms 141132 KB Output is correct
9 Correct 58 ms 141156 KB Output is correct
10 Correct 60 ms 141116 KB Output is correct
11 Correct 468 ms 145876 KB Output is correct
12 Correct 451 ms 146272 KB Output is correct
13 Correct 469 ms 145828 KB Output is correct
14 Correct 480 ms 145892 KB Output is correct
15 Correct 439 ms 146140 KB Output is correct
16 Correct 472 ms 146352 KB Output is correct
17 Correct 472 ms 146400 KB Output is correct
18 Correct 458 ms 146360 KB Output is correct
19 Correct 419 ms 145460 KB Output is correct
20 Correct 421 ms 145596 KB Output is correct
21 Correct 441 ms 145512 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 145212 KB Output is correct
2 Correct 243 ms 144588 KB Output is correct
3 Correct 239 ms 144460 KB Output is correct
4 Correct 239 ms 144512 KB Output is correct
5 Correct 245 ms 144548 KB Output is correct
6 Correct 246 ms 144548 KB Output is correct
7 Correct 238 ms 144480 KB Output is correct
8 Correct 61 ms 141172 KB Output is correct
9 Correct 58 ms 141192 KB Output is correct
10 Correct 59 ms 141152 KB Output is correct
11 Correct 930 ms 150196 KB Output is correct
12 Correct 929 ms 153648 KB Output is correct
13 Correct 929 ms 150088 KB Output is correct
14 Correct 950 ms 150236 KB Output is correct
15 Correct 949 ms 153292 KB Output is correct
16 Correct 963 ms 153464 KB Output is correct
17 Correct 938 ms 153524 KB Output is correct
18 Correct 957 ms 153752 KB Output is correct
19 Correct 923 ms 153652 KB Output is correct
20 Correct 904 ms 153404 KB Output is correct
21 Correct 910 ms 153628 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 146208 KB Output is correct
2 Correct 154 ms 143220 KB Output is correct
3 Correct 134 ms 143276 KB Output is correct
4 Correct 132 ms 143280 KB Output is correct
5 Correct 135 ms 143328 KB Output is correct
6 Correct 135 ms 143368 KB Output is correct
7 Correct 143 ms 143388 KB Output is correct
8 Correct 57 ms 141132 KB Output is correct
9 Correct 58 ms 141156 KB Output is correct
10 Correct 60 ms 141116 KB Output is correct
11 Correct 468 ms 145876 KB Output is correct
12 Correct 451 ms 146272 KB Output is correct
13 Correct 469 ms 145828 KB Output is correct
14 Correct 480 ms 145892 KB Output is correct
15 Correct 439 ms 146140 KB Output is correct
16 Correct 472 ms 146352 KB Output is correct
17 Correct 472 ms 146400 KB Output is correct
18 Correct 458 ms 146360 KB Output is correct
19 Correct 419 ms 145460 KB Output is correct
20 Correct 421 ms 145596 KB Output is correct
21 Correct 441 ms 145512 KB Output is correct
22 Correct 998 ms 145484 KB Output is correct
23 Correct 222 ms 142844 KB Output is correct
24 Correct 224 ms 143036 KB Output is correct
25 Correct 220 ms 142912 KB Output is correct
26 Correct 225 ms 142872 KB Output is correct
27 Correct 252 ms 142880 KB Output is correct
28 Correct 228 ms 142816 KB Output is correct
29 Correct 58 ms 141184 KB Output is correct
30 Correct 59 ms 141204 KB Output is correct
31 Correct 60 ms 141104 KB Output is correct
32 Correct 1070 ms 145416 KB Output is correct
33 Correct 999 ms 145448 KB Output is correct
34 Correct 1014 ms 145684 KB Output is correct
35 Correct 1070 ms 145512 KB Output is correct
36 Correct 816 ms 145736 KB Output is correct
37 Correct 812 ms 145620 KB Output is correct
38 Correct 808 ms 145664 KB Output is correct
39 Correct 1049 ms 145244 KB Output is correct
40 Correct 1052 ms 145264 KB Output is correct
41 Correct 1035 ms 145076 KB Output is correct
42 Correct 1016 ms 145100 KB Output is correct
43 Correct 1012 ms 145224 KB Output is correct
44 Correct 1004 ms 144904 KB Output is correct
45 Correct 1008 ms 144800 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 145816 KB Output is correct
2 Correct 169 ms 142944 KB Output is correct
3 Correct 173 ms 142992 KB Output is correct
4 Correct 169 ms 143164 KB Output is correct
5 Correct 174 ms 143148 KB Output is correct
6 Correct 190 ms 143180 KB Output is correct
7 Correct 166 ms 143132 KB Output is correct
8 Correct 55 ms 141132 KB Output is correct
9 Correct 59 ms 141120 KB Output is correct
10 Correct 68 ms 141132 KB Output is correct
11 Correct 511 ms 145828 KB Output is correct
12 Correct 516 ms 145704 KB Output is correct
13 Correct 507 ms 146116 KB Output is correct
14 Correct 502 ms 146104 KB Output is correct
15 Correct 512 ms 145988 KB Output is correct
16 Correct 508 ms 145760 KB Output is correct
17 Correct 517 ms 145736 KB Output is correct
18 Correct 506 ms 145788 KB Output is correct
19 Incorrect 62 ms 141132 KB Output isn't correct
20 Halted 0 ms 0 KB -