oj.uz

Submission #736563

# Submission time Handle Problem Language Result Execution time Memory
736563 2023-05-06T00:12:12 Z Ronin13 Progression (NOI20_progression) C++14
68 / 100
 1124 ms 145016 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 = -9e18;
        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 == -9e18)return;
    t[v * 2].lazy = t[v].lazy;
    t[v * 2].lazy1 = 0;
    t[v * 2 + 1].lazy = t[v].lazy;
    t[v * 2 + 1].lazy1 = 0;
    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 = -9e18;
    t[v].lazy1 = 0;
}

void push2(int v, int l, int r){
    if(t[v].lazy1 == 0) return;
    ll m = (l + r) / 2;
    if(t[v * 2].lazy != -9e18) t[v * 2].lazy += t[v].lazy1;
    if(t[v * 2 + 1].lazy != -9e18) 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 != -9e18) 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 = -9e18;
        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;

            ll val = s + c * (r - l);
            val = -val + getsum(1, 1, n, r, r);
            if(r != n)upd_p(1, 1, n, r, val);
            updran2(1,1, n, l, r - 1, c);
        }
        if(t == 2){
            ll l, r, s, c; cin >> l >> r >> s >> c;

            ll y =  getsum(1, 1, n, 1, r) + a[1];
            if(l > 1){
                ll x = getsum(1, 1, n, 1, l - 2) + a[1];
                upd_p(1, 1, n, l - 1, s - x);
            }
            if(r < n){
                ll 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 532 ms 144112 KB Output is correct
2 Correct 179 ms 141464 KB Output is correct
3 Correct 168 ms 141484 KB Output is correct
4 Correct 169 ms 141396 KB Output is correct
5 Correct 170 ms 141520 KB Output is correct
6 Correct 183 ms 141472 KB Output is correct
7 Correct 175 ms 141448 KB Output is correct
8 Correct 58 ms 141132 KB Output is correct
9 Correct 61 ms 141120 KB Output is correct
10 Correct 65 ms 141168 KB Output is correct
11 Correct 508 ms 144244 KB Output is correct
12 Correct 508 ms 144288 KB Output is correct
13 Correct 524 ms 144436 KB Output is correct
14 Correct 554 ms 144396 KB Output is correct
15 Correct 588 ms 144436 KB Output is correct
16 Correct 548 ms 144128 KB Output is correct
17 Correct 532 ms 144192 KB Output is correct
18 Correct 543 ms 144064 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141144 KB Output is correct
2 Incorrect 58 ms 141132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 144588 KB Output is correct
2 Correct 144 ms 141740 KB Output is correct
3 Correct 150 ms 141684 KB Output is correct
4 Correct 154 ms 141772 KB Output is correct
5 Correct 148 ms 141796 KB Output is correct
6 Correct 146 ms 141800 KB Output is correct
7 Correct 133 ms 141868 KB Output is correct
8 Correct 62 ms 141128 KB Output is correct
9 Correct 59 ms 141132 KB Output is correct
10 Correct 58 ms 141132 KB Output is correct
11 Correct 472 ms 144320 KB Output is correct
12 Correct 503 ms 144688 KB Output is correct
13 Correct 480 ms 144316 KB Output is correct
14 Correct 515 ms 144300 KB Output is correct
15 Correct 454 ms 144524 KB Output is correct
16 Correct 496 ms 144916 KB Output is correct
17 Correct 493 ms 145016 KB Output is correct
18 Correct 463 ms 144916 KB Output is correct
19 Correct 418 ms 144284 KB Output is correct
20 Correct 542 ms 144192 KB Output is correct
21 Correct 439 ms 144260 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 143808 KB Output is correct
2 Correct 232 ms 141388 KB Output is correct
3 Correct 258 ms 141492 KB Output is correct
4 Correct 260 ms 141424 KB Output is correct
5 Correct 245 ms 141372 KB Output is correct
6 Correct 247 ms 141432 KB Output is correct
7 Correct 246 ms 141408 KB Output is correct
8 Correct 56 ms 141192 KB Output is correct
9 Correct 71 ms 141128 KB Output is correct
10 Correct 60 ms 141156 KB Output is correct
11 Correct 1020 ms 143908 KB Output is correct
12 Correct 1062 ms 144060 KB Output is correct
13 Correct 1016 ms 143764 KB Output is correct
14 Correct 998 ms 143948 KB Output is correct
15 Correct 923 ms 143848 KB Output is correct
16 Correct 1055 ms 143912 KB Output is correct
17 Correct 1038 ms 143844 KB Output is correct
18 Correct 983 ms 143804 KB Output is correct
19 Correct 977 ms 143816 KB Output is correct
20 Correct 916 ms 143696 KB Output is correct
21 Correct 937 ms 143832 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 144588 KB Output is correct
2 Correct 144 ms 141740 KB Output is correct
3 Correct 150 ms 141684 KB Output is correct
4 Correct 154 ms 141772 KB Output is correct
5 Correct 148 ms 141796 KB Output is correct
6 Correct 146 ms 141800 KB Output is correct
7 Correct 133 ms 141868 KB Output is correct
8 Correct 62 ms 141128 KB Output is correct
9 Correct 59 ms 141132 KB Output is correct
10 Correct 58 ms 141132 KB Output is correct
11 Correct 472 ms 144320 KB Output is correct
12 Correct 503 ms 144688 KB Output is correct
13 Correct 480 ms 144316 KB Output is correct
14 Correct 515 ms 144300 KB Output is correct
15 Correct 454 ms 144524 KB Output is correct
16 Correct 496 ms 144916 KB Output is correct
17 Correct 493 ms 145016 KB Output is correct
18 Correct 463 ms 144916 KB Output is correct
19 Correct 418 ms 144284 KB Output is correct
20 Correct 542 ms 144192 KB Output is correct
21 Correct 439 ms 144260 KB Output is correct
22 Correct 1066 ms 143996 KB Output is correct
23 Correct 251 ms 141448 KB Output is correct
24 Correct 223 ms 141392 KB Output is correct
25 Correct 277 ms 141500 KB Output is correct
26 Correct 225 ms 141524 KB Output is correct
27 Correct 234 ms 141408 KB Output is correct
28 Correct 230 ms 141476 KB Output is correct
29 Correct 63 ms 141128 KB Output is correct
30 Correct 56 ms 141108 KB Output is correct
31 Correct 63 ms 141156 KB Output is correct
32 Correct 1047 ms 144160 KB Output is correct
33 Correct 1004 ms 143912 KB Output is correct
34 Correct 1025 ms 143928 KB Output is correct
35 Correct 1064 ms 144052 KB Output is correct
36 Correct 808 ms 144188 KB Output is correct
37 Correct 829 ms 144276 KB Output is correct
38 Correct 810 ms 144112 KB Output is correct
39 Correct 1049 ms 143948 KB Output is correct
40 Correct 1124 ms 144100 KB Output is correct
41 Correct 1121 ms 144116 KB Output is correct
42 Correct 1121 ms 143952 KB Output is correct
43 Correct 1040 ms 143852 KB Output is correct
44 Correct 1082 ms 143960 KB Output is correct
45 Correct 1029 ms 143872 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 144112 KB Output is correct
2 Correct 179 ms 141464 KB Output is correct
3 Correct 168 ms 141484 KB Output is correct
4 Correct 169 ms 141396 KB Output is correct
5 Correct 170 ms 141520 KB Output is correct
6 Correct 183 ms 141472 KB Output is correct
7 Correct 175 ms 141448 KB Output is correct
8 Correct 58 ms 141132 KB Output is correct
9 Correct 61 ms 141120 KB Output is correct
10 Correct 65 ms 141168 KB Output is correct
11 Correct 508 ms 144244 KB Output is correct
12 Correct 508 ms 144288 KB Output is correct
13 Correct 524 ms 144436 KB Output is correct
14 Correct 554 ms 144396 KB Output is correct
15 Correct 588 ms 144436 KB Output is correct
16 Correct 548 ms 144128 KB Output is correct
17 Correct 532 ms 144192 KB Output is correct
18 Correct 543 ms 144064 KB Output is correct
19 Correct 58 ms 141144 KB Output is correct
20 Incorrect 58 ms 141132 KB Output isn't correct
21 Halted 0 ms 0 KB -