oj.uz

Submission #736560

# Submission time Handle Problem Language Result Execution time Memory
736560 2023-05-06T00:00:22 Z Ronin13 Progression (NOI20_progression) C++14
68 / 100
 1088 ms 148412 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 = 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 = -1e18;
    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 != -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;

            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 521 ms 147936 KB Output is correct
2 Correct 169 ms 144396 KB Output is correct
3 Correct 181 ms 144404 KB Output is correct
4 Correct 172 ms 144352 KB Output is correct
5 Correct 174 ms 144512 KB Output is correct
6 Correct 178 ms 144496 KB Output is correct
7 Correct 170 ms 144424 KB Output is correct
8 Correct 57 ms 141132 KB Output is correct
9 Correct 59 ms 141160 KB Output is correct
10 Correct 59 ms 141104 KB Output is correct
11 Correct 509 ms 147872 KB Output is correct
12 Correct 522 ms 147636 KB Output is correct
13 Correct 538 ms 147892 KB Output is correct
14 Correct 539 ms 147900 KB Output is correct
15 Correct 525 ms 147904 KB Output is correct
16 Correct 527 ms 147820 KB Output is correct
17 Correct 524 ms 147700 KB Output is correct
18 Correct 524 ms 147704 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 141204 KB Output is correct
2 Incorrect 59 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 559 ms 147976 KB Output is correct
2 Correct 134 ms 143868 KB Output is correct
3 Correct 147 ms 143936 KB Output is correct
4 Correct 126 ms 143796 KB Output is correct
5 Correct 148 ms 143944 KB Output is correct
6 Correct 143 ms 143936 KB Output is correct
7 Correct 138 ms 143976 KB Output is correct
8 Correct 56 ms 141132 KB Output is correct
9 Correct 54 ms 141092 KB Output is correct
10 Correct 60 ms 141100 KB Output is correct
11 Correct 491 ms 147796 KB Output is correct
12 Correct 454 ms 148108 KB Output is correct
13 Correct 518 ms 147780 KB Output is correct
14 Correct 469 ms 147744 KB Output is correct
15 Correct 461 ms 148116 KB Output is correct
16 Correct 491 ms 148412 KB Output is correct
17 Correct 487 ms 148172 KB Output is correct
18 Correct 516 ms 148280 KB Output is correct
19 Correct 459 ms 147348 KB Output is correct
20 Correct 465 ms 147664 KB Output is correct
21 Correct 431 ms 147260 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 146872 KB Output is correct
2 Correct 237 ms 143560 KB Output is correct
3 Correct 246 ms 143436 KB Output is correct
4 Correct 242 ms 143380 KB Output is correct
5 Correct 247 ms 143408 KB Output is correct
6 Correct 259 ms 143448 KB Output is correct
7 Correct 245 ms 143532 KB Output is correct
8 Correct 56 ms 141128 KB Output is correct
9 Correct 61 ms 141212 KB Output is correct
10 Correct 65 ms 141184 KB Output is correct
11 Correct 988 ms 145804 KB Output is correct
12 Correct 1000 ms 145936 KB Output is correct
13 Correct 943 ms 145872 KB Output is correct
14 Correct 944 ms 145760 KB Output is correct
15 Correct 902 ms 145636 KB Output is correct
16 Correct 931 ms 145516 KB Output is correct
17 Correct 946 ms 145600 KB Output is correct
18 Correct 946 ms 145700 KB Output is correct
19 Correct 927 ms 145252 KB Output is correct
20 Correct 950 ms 145244 KB Output is correct
21 Correct 932 ms 145600 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 147976 KB Output is correct
2 Correct 134 ms 143868 KB Output is correct
3 Correct 147 ms 143936 KB Output is correct
4 Correct 126 ms 143796 KB Output is correct
5 Correct 148 ms 143944 KB Output is correct
6 Correct 143 ms 143936 KB Output is correct
7 Correct 138 ms 143976 KB Output is correct
8 Correct 56 ms 141132 KB Output is correct
9 Correct 54 ms 141092 KB Output is correct
10 Correct 60 ms 141100 KB Output is correct
11 Correct 491 ms 147796 KB Output is correct
12 Correct 454 ms 148108 KB Output is correct
13 Correct 518 ms 147780 KB Output is correct
14 Correct 469 ms 147744 KB Output is correct
15 Correct 461 ms 148116 KB Output is correct
16 Correct 491 ms 148412 KB Output is correct
17 Correct 487 ms 148172 KB Output is correct
18 Correct 516 ms 148280 KB Output is correct
19 Correct 459 ms 147348 KB Output is correct
20 Correct 465 ms 147664 KB Output is correct
21 Correct 431 ms 147260 KB Output is correct
22 Correct 1014 ms 147160 KB Output is correct
23 Correct 225 ms 144460 KB Output is correct
24 Correct 225 ms 144244 KB Output is correct
25 Correct 231 ms 144532 KB Output is correct
26 Correct 229 ms 144480 KB Output is correct
27 Correct 236 ms 144332 KB Output is correct
28 Correct 245 ms 144412 KB Output is correct
29 Correct 58 ms 141156 KB Output is correct
30 Correct 58 ms 141168 KB Output is correct
31 Correct 55 ms 141228 KB Output is correct
32 Correct 1020 ms 146828 KB Output is correct
33 Correct 1006 ms 146704 KB Output is correct
34 Correct 1059 ms 146668 KB Output is correct
35 Correct 1014 ms 146648 KB Output is correct
36 Correct 803 ms 146936 KB Output is correct
37 Correct 795 ms 146936 KB Output is correct
38 Correct 805 ms 146884 KB Output is correct
39 Correct 1045 ms 146600 KB Output is correct
40 Correct 1020 ms 146700 KB Output is correct
41 Correct 1041 ms 146508 KB Output is correct
42 Correct 1041 ms 146528 KB Output is correct
43 Correct 988 ms 146252 KB Output is correct
44 Correct 990 ms 146380 KB Output is correct
45 Correct 1088 ms 146220 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 147936 KB Output is correct
2 Correct 169 ms 144396 KB Output is correct
3 Correct 181 ms 144404 KB Output is correct
4 Correct 172 ms 144352 KB Output is correct
5 Correct 174 ms 144512 KB Output is correct
6 Correct 178 ms 144496 KB Output is correct
7 Correct 170 ms 144424 KB Output is correct
8 Correct 57 ms 141132 KB Output is correct
9 Correct 59 ms 141160 KB Output is correct
10 Correct 59 ms 141104 KB Output is correct
11 Correct 509 ms 147872 KB Output is correct
12 Correct 522 ms 147636 KB Output is correct
13 Correct 538 ms 147892 KB Output is correct
14 Correct 539 ms 147900 KB Output is correct
15 Correct 525 ms 147904 KB Output is correct
16 Correct 527 ms 147820 KB Output is correct
17 Correct 524 ms 147700 KB Output is correct
18 Correct 524 ms 147704 KB Output is correct
19 Correct 59 ms 141204 KB Output is correct
20 Incorrect 59 ms 141132 KB Output isn't correct
21 Halted 0 ms 0 KB -