oj.uz

Submission #736566

# Submission time Handle Problem Language Result Execution time Memory
736566 2023-05-06T00:34:46 Z Ronin13 Progression (NOI20_progression) C++14
68 / 100
 1033 ms 145056 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(l == 1){
                a[1] = s;
            }
            updran1(1, 1, n, l, r - 1, c);
            if(r < n){
                ll x = y;
                upd_p(1, 1, n, r, x - s - (r - l) * c);
            }
        }
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 144188 KB Output is correct
2 Correct 176 ms 141524 KB Output is correct
3 Correct 163 ms 141460 KB Output is correct
4 Correct 169 ms 141404 KB Output is correct
5 Correct 160 ms 141628 KB Output is correct
6 Correct 170 ms 141552 KB Output is correct
7 Correct 165 ms 141472 KB Output is correct
8 Correct 54 ms 141132 KB Output is correct
9 Correct 57 ms 141164 KB Output is correct
10 Correct 55 ms 141164 KB Output is correct
11 Correct 504 ms 144316 KB Output is correct
12 Correct 532 ms 144060 KB Output is correct
13 Correct 525 ms 144348 KB Output is correct
14 Correct 595 ms 144316 KB Output is correct
15 Correct 488 ms 144320 KB Output is correct
16 Correct 502 ms 144196 KB Output is correct
17 Correct 547 ms 144092 KB Output is correct
18 Correct 522 ms 144104 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 141168 KB Output is correct
2 Incorrect 66 ms 141140 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 444 ms 144596 KB Output is correct
2 Correct 135 ms 141776 KB Output is correct
3 Correct 129 ms 141772 KB Output is correct
4 Correct 129 ms 141772 KB Output is correct
5 Correct 135 ms 141840 KB Output is correct
6 Correct 153 ms 141844 KB Output is correct
7 Correct 138 ms 141852 KB Output is correct
8 Correct 56 ms 141128 KB Output is correct
9 Correct 55 ms 141104 KB Output is correct
10 Correct 57 ms 141148 KB Output is correct
11 Correct 495 ms 144384 KB Output is correct
12 Correct 450 ms 144544 KB Output is correct
13 Correct 481 ms 144332 KB Output is correct
14 Correct 491 ms 144332 KB Output is correct
15 Correct 443 ms 144496 KB Output is correct
16 Correct 473 ms 145056 KB Output is correct
17 Correct 488 ms 144956 KB Output is correct
18 Correct 478 ms 145012 KB Output is correct
19 Correct 423 ms 144224 KB Output is correct
20 Correct 425 ms 144208 KB Output is correct
21 Correct 444 ms 144196 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 143796 KB Output is correct
2 Correct 236 ms 141392 KB Output is correct
3 Correct 243 ms 141376 KB Output is correct
4 Correct 237 ms 141388 KB Output is correct
5 Correct 269 ms 141492 KB Output is correct
6 Correct 242 ms 141380 KB Output is correct
7 Correct 242 ms 141460 KB Output is correct
8 Correct 55 ms 141116 KB Output is correct
9 Correct 55 ms 141124 KB Output is correct
10 Correct 57 ms 141088 KB Output is correct
11 Correct 922 ms 143940 KB Output is correct
12 Correct 909 ms 143868 KB Output is correct
13 Correct 907 ms 143864 KB Output is correct
14 Correct 901 ms 143804 KB Output is correct
15 Correct 873 ms 143720 KB Output is correct
16 Correct 942 ms 143844 KB Output is correct
17 Correct 925 ms 143952 KB Output is correct
18 Correct 920 ms 143852 KB Output is correct
19 Correct 909 ms 143968 KB Output is correct
20 Correct 922 ms 143848 KB Output is correct
21 Correct 910 ms 143908 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 144596 KB Output is correct
2 Correct 135 ms 141776 KB Output is correct
3 Correct 129 ms 141772 KB Output is correct
4 Correct 129 ms 141772 KB Output is correct
5 Correct 135 ms 141840 KB Output is correct
6 Correct 153 ms 141844 KB Output is correct
7 Correct 138 ms 141852 KB Output is correct
8 Correct 56 ms 141128 KB Output is correct
9 Correct 55 ms 141104 KB Output is correct
10 Correct 57 ms 141148 KB Output is correct
11 Correct 495 ms 144384 KB Output is correct
12 Correct 450 ms 144544 KB Output is correct
13 Correct 481 ms 144332 KB Output is correct
14 Correct 491 ms 144332 KB Output is correct
15 Correct 443 ms 144496 KB Output is correct
16 Correct 473 ms 145056 KB Output is correct
17 Correct 488 ms 144956 KB Output is correct
18 Correct 478 ms 145012 KB Output is correct
19 Correct 423 ms 144224 KB Output is correct
20 Correct 425 ms 144208 KB Output is correct
21 Correct 444 ms 144196 KB Output is correct
22 Correct 993 ms 144052 KB Output is correct
23 Correct 241 ms 141464 KB Output is correct
24 Correct 221 ms 141548 KB Output is correct
25 Correct 220 ms 141488 KB Output is correct
26 Correct 221 ms 141408 KB Output is correct
27 Correct 233 ms 141472 KB Output is correct
28 Correct 221 ms 141492 KB Output is correct
29 Correct 54 ms 141140 KB Output is correct
30 Correct 54 ms 141092 KB Output is correct
31 Correct 62 ms 141136 KB Output is correct
32 Correct 1004 ms 143972 KB Output is correct
33 Correct 1006 ms 144064 KB Output is correct
34 Correct 1026 ms 143936 KB Output is correct
35 Correct 1016 ms 144036 KB Output is correct
36 Correct 841 ms 144148 KB Output is correct
37 Correct 807 ms 144176 KB Output is correct
38 Correct 822 ms 144304 KB Output is correct
39 Correct 988 ms 144024 KB Output is correct
40 Correct 1033 ms 143932 KB Output is correct
41 Correct 1008 ms 144112 KB Output is correct
42 Correct 1004 ms 144076 KB Output is correct
43 Correct 973 ms 143996 KB Output is correct
44 Correct 989 ms 144128 KB Output is correct
45 Correct 986 ms 143980 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 144188 KB Output is correct
2 Correct 176 ms 141524 KB Output is correct
3 Correct 163 ms 141460 KB Output is correct
4 Correct 169 ms 141404 KB Output is correct
5 Correct 160 ms 141628 KB Output is correct
6 Correct 170 ms 141552 KB Output is correct
7 Correct 165 ms 141472 KB Output is correct
8 Correct 54 ms 141132 KB Output is correct
9 Correct 57 ms 141164 KB Output is correct
10 Correct 55 ms 141164 KB Output is correct
11 Correct 504 ms 144316 KB Output is correct
12 Correct 532 ms 144060 KB Output is correct
13 Correct 525 ms 144348 KB Output is correct
14 Correct 595 ms 144316 KB Output is correct
15 Correct 488 ms 144320 KB Output is correct
16 Correct 502 ms 144196 KB Output is correct
17 Correct 547 ms 144092 KB Output is correct
18 Correct 522 ms 144104 KB Output is correct
19 Correct 58 ms 141168 KB Output is correct
20 Incorrect 66 ms 141140 KB Output isn't correct
21 Halted 0 ms 0 KB -