oj.uz

Submission #736554

# Submission time Handle Problem Language Result Execution time Memory
736554 2023-05-05T23:44:02 Z Ronin13 Progression (NOI20_progression) C++14
68 / 100
 1069 ms 146036 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 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 488 ms 145484 KB Output is correct
2 Correct 162 ms 142768 KB Output is correct
3 Correct 161 ms 142684 KB Output is correct
4 Correct 171 ms 142548 KB Output is correct
5 Correct 164 ms 142484 KB Output is correct
6 Correct 161 ms 142532 KB Output is correct
7 Correct 159 ms 142516 KB Output is correct
8 Correct 54 ms 141216 KB Output is correct
9 Correct 57 ms 141120 KB Output is correct
10 Correct 61 ms 141164 KB Output is correct
11 Correct 489 ms 144936 KB Output is correct
12 Correct 495 ms 144976 KB Output is correct
13 Correct 506 ms 145184 KB Output is correct
14 Correct 520 ms 145228 KB Output is correct
15 Correct 494 ms 145184 KB Output is correct
16 Correct 500 ms 144820 KB Output is correct
17 Correct 497 ms 144844 KB Output is correct
18 Correct 493 ms 145308 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 141136 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 443 ms 145608 KB Output is correct
2 Correct 133 ms 142796 KB Output is correct
3 Correct 133 ms 142796 KB Output is correct
4 Correct 130 ms 142916 KB Output is correct
5 Correct 131 ms 142796 KB Output is correct
6 Correct 139 ms 142880 KB Output is correct
7 Correct 134 ms 142796 KB Output is correct
8 Correct 55 ms 141196 KB Output is correct
9 Correct 55 ms 141104 KB Output is correct
10 Correct 57 ms 141180 KB Output is correct
11 Correct 450 ms 145388 KB Output is correct
12 Correct 443 ms 145592 KB Output is correct
13 Correct 456 ms 145356 KB Output is correct
14 Correct 453 ms 145424 KB Output is correct
15 Correct 437 ms 145488 KB Output is correct
16 Correct 466 ms 145872 KB Output is correct
17 Correct 496 ms 145988 KB Output is correct
18 Correct 463 ms 146036 KB Output is correct
19 Correct 419 ms 145248 KB Output is correct
20 Correct 413 ms 145116 KB Output is correct
21 Correct 425 ms 145064 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 144608 KB Output is correct
2 Correct 242 ms 141980 KB Output is correct
3 Correct 233 ms 141964 KB Output is correct
4 Correct 238 ms 142028 KB Output is correct
5 Correct 251 ms 142040 KB Output is correct
6 Correct 231 ms 142012 KB Output is correct
7 Correct 238 ms 141992 KB Output is correct
8 Correct 54 ms 141152 KB Output is correct
9 Correct 62 ms 141176 KB Output is correct
10 Correct 62 ms 141164 KB Output is correct
11 Correct 941 ms 144596 KB Output is correct
12 Correct 949 ms 144636 KB Output is correct
13 Correct 939 ms 144436 KB Output is correct
14 Correct 933 ms 144556 KB Output is correct
15 Correct 898 ms 144412 KB Output is correct
16 Correct 953 ms 144604 KB Output is correct
17 Correct 934 ms 144548 KB Output is correct
18 Correct 944 ms 144740 KB Output is correct
19 Correct 909 ms 144464 KB Output is correct
20 Correct 920 ms 144356 KB Output is correct
21 Correct 941 ms 144336 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 145608 KB Output is correct
2 Correct 133 ms 142796 KB Output is correct
3 Correct 133 ms 142796 KB Output is correct
4 Correct 130 ms 142916 KB Output is correct
5 Correct 131 ms 142796 KB Output is correct
6 Correct 139 ms 142880 KB Output is correct
7 Correct 134 ms 142796 KB Output is correct
8 Correct 55 ms 141196 KB Output is correct
9 Correct 55 ms 141104 KB Output is correct
10 Correct 57 ms 141180 KB Output is correct
11 Correct 450 ms 145388 KB Output is correct
12 Correct 443 ms 145592 KB Output is correct
13 Correct 456 ms 145356 KB Output is correct
14 Correct 453 ms 145424 KB Output is correct
15 Correct 437 ms 145488 KB Output is correct
16 Correct 466 ms 145872 KB Output is correct
17 Correct 496 ms 145988 KB Output is correct
18 Correct 463 ms 146036 KB Output is correct
19 Correct 419 ms 145248 KB Output is correct
20 Correct 413 ms 145116 KB Output is correct
21 Correct 425 ms 145064 KB Output is correct
22 Correct 1010 ms 144848 KB Output is correct
23 Correct 229 ms 142224 KB Output is correct
24 Correct 221 ms 141920 KB Output is correct
25 Correct 218 ms 142060 KB Output is correct
26 Correct 228 ms 142016 KB Output is correct
27 Correct 230 ms 142000 KB Output is correct
28 Correct 236 ms 142044 KB Output is correct
29 Correct 60 ms 141132 KB Output is correct
30 Correct 58 ms 141124 KB Output is correct
31 Correct 61 ms 141132 KB Output is correct
32 Correct 1046 ms 144488 KB Output is correct
33 Correct 1000 ms 144408 KB Output is correct
34 Correct 1030 ms 144520 KB Output is correct
35 Correct 1069 ms 144400 KB Output is correct
36 Correct 822 ms 144500 KB Output is correct
37 Correct 808 ms 144416 KB Output is correct
38 Correct 818 ms 144612 KB Output is correct
39 Correct 999 ms 144464 KB Output is correct
40 Correct 1022 ms 144232 KB Output is correct
41 Correct 1042 ms 144360 KB Output is correct
42 Correct 1040 ms 144400 KB Output is correct
43 Correct 994 ms 144184 KB Output is correct
44 Correct 1006 ms 144260 KB Output is correct
45 Correct 1004 ms 144180 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 145484 KB Output is correct
2 Correct 162 ms 142768 KB Output is correct
3 Correct 161 ms 142684 KB Output is correct
4 Correct 171 ms 142548 KB Output is correct
5 Correct 164 ms 142484 KB Output is correct
6 Correct 161 ms 142532 KB Output is correct
7 Correct 159 ms 142516 KB Output is correct
8 Correct 54 ms 141216 KB Output is correct
9 Correct 57 ms 141120 KB Output is correct
10 Correct 61 ms 141164 KB Output is correct
11 Correct 489 ms 144936 KB Output is correct
12 Correct 495 ms 144976 KB Output is correct
13 Correct 506 ms 145184 KB Output is correct
14 Correct 520 ms 145228 KB Output is correct
15 Correct 494 ms 145184 KB Output is correct
16 Correct 500 ms 144820 KB Output is correct
17 Correct 497 ms 144844 KB Output is correct
18 Correct 493 ms 145308 KB Output is correct
19 Incorrect 58 ms 141136 KB Output isn't correct
20 Halted 0 ms 0 KB -