oj.uz

Submission #1081527

# Submission time Handle Problem Language Result Execution time Memory
1081527 2024-08-30T07:05:17 Z _callmelucian Progression (NOI20_progression) C++14
68 / 100
 807 ms 104424 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct node {
    ll lazyAsgn, lazyAdd, sum;
    ll best, preLen, preVal, sufLen, sufVal, same, len;

    node() : lazyAsgn(0), lazyAdd(0), sum(0), best(0), preLen(0), preVal(0), sufLen(0), sufVal(0), same(0), len(0) {}

    void refine (node ln, node rn) {
        best = max({ln.best, rn.best, (ln.sufLen + rn.preLen) * (ln.sufVal == rn.preVal)});
        preLen = max(ln.preLen, (ln.len + rn.preLen) * (ln.same == rn.preVal));
        preVal = ln.preVal;
        sufLen = max(rn.sufLen, (ln.sufLen + rn.len) * (ln.sufVal == rn.same));
        sufVal = rn.sufVal;
        same = (ln.same == rn.same ? ln.same : LLONG_MAX);
        sum = ln.sum + rn.sum, len = ln.len + rn.len;
    }

    void applyAsgn (ll val, int l, int r) {
        lazyAsgn = val, lazyAdd = 0, sum = val * ll(r - l + 1);
        best = preLen = sufLen = r - l + 1;
        preVal = sufVal = same = val, len = r - l + 1;
    }

    void applyAdd (ll incr, int l, int r) {
        lazyAdd += incr, sum += incr * ll(r - l + 1);
        preVal += incr, sufVal += incr, len = r - l + 1;
        if (same != LLONG_MAX) same += incr;
    }

    void pushDown (node &ln, node &rn, int l, int r, int mid) {
        if (lazyAsgn != LLONG_MAX) {
            ln.applyAsgn(lazyAsgn, l, mid);
            rn.applyAsgn(lazyAsgn, mid + 1, r);
        }
        if (lazyAdd != 0) {
            ln.applyAdd(lazyAdd, l, mid);
            rn.applyAdd(lazyAdd, mid + 1, r);
        }
        lazyAsgn = LLONG_MAX, lazyAdd = 0;
    }
};

struct IT {
    vector<node> tr;
    IT (int sz) : tr(4 * sz) {}

    void rangeAssign (int a, int b, ll val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            tr[k].applyAsgn(val, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        rangeAssign(a, b, val, 2 * k, l, mid);
        rangeAssign(a, b, val, 2 * k + 1, mid + 1, r);
        tr[k].refine(tr[2 * k], tr[2 * k + 1]);
    }

    void rangeAdd (int a, int b, ll incr, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            tr[k].applyAdd(incr, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        rangeAdd(a, b, incr, 2 * k, l, mid);
        rangeAdd(a, b, incr, 2 * k + 1, mid + 1, r);
        tr[k].refine(tr[2 * k], tr[2 * k + 1]);
    }

    ll querySum (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return tr[k].sum;
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        return querySum(a, b, 2 * k, l, mid) + querySum(a, b, 2 * k + 1, mid + 1, r);
    }

    node query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return node();
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        tr[k].pushDown(tr[2 * k], tr[2 * k + 1], l, r, mid);
        node ans; ans.refine(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
        return ans;
    }

    ll longestSame (int a, int b, int k, int l, int r) {
        return query(a, b, k, l, r).best;
    }

    void lineAssign (int a, int b, ll S, ll C, int k, int l, int r) {
        if (b < r) {
            ll incrR = querySum(1, b + 1, k, l, r) - S + ll(b - a) * C;
            rangeAssign(b + 1, b + 1, incrR, k, l, r);
        }
        ll incrL = S - (a == l ? 0 : querySum(1, a - 1, k, l, r));
        rangeAssign(a, a, incrL, k, l, r);
        if (a < b) rangeAssign(a + 1, b, C, k, l, r);
    }

    void lineAdd (int a, int b, ll S, ll C, int k, int l, int r) {
        if (b < r)
            rangeAdd(b + 1, b + 1, -(S + ll(b - a) * C), k, l, r);
        rangeAdd(a, a, S, k, l, r);
        if (a < b) rangeAdd(a + 1, b, C, k, l, r);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    IT tree(n);

    for (int i = 1; i <= n; i++) {
        int D; cin >> D;
        tree.lineAssign(i, i, D, 0, 1, 1, n);
    }

    while (q--) {
        int type, L, R; cin >> type >> L >> R;
        if (type == 1) {
            int S, C; cin >> S >> C;
            tree.lineAdd(L, R, S, C, 1, 1, n);
        }
        else if (type == 2) {
            int S, C; cin >> S >> C;
            tree.lineAssign(L, R, S, C, 1, 1, n);
        }
        else {
            if (L == R) cout << 1 << "\n";
            else cout << tree.longestSame(L + 1, R, 1, 1, n) + 1 << "\n";
        }
    }

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 102808 KB Output is correct
2 Correct 83 ms 3920 KB Output is correct
3 Correct 86 ms 3464 KB Output is correct
4 Correct 85 ms 3664 KB Output is correct
5 Correct 84 ms 3660 KB Output is correct
6 Correct 87 ms 3720 KB Output is correct
7 Correct 89 ms 3664 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 537 ms 102804 KB Output is correct
12 Correct 485 ms 102736 KB Output is correct
13 Correct 486 ms 103248 KB Output is correct
14 Correct 491 ms 103440 KB Output is correct
15 Correct 489 ms 102992 KB Output is correct
16 Correct 477 ms 102948 KB Output is correct
17 Correct 469 ms 102700 KB Output is correct
18 Correct 474 ms 102736 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 101428 KB Output is correct
2 Correct 67 ms 3152 KB Output is correct
3 Correct 63 ms 3140 KB Output is correct
4 Correct 52 ms 2896 KB Output is correct
5 Correct 90 ms 3080 KB Output is correct
6 Correct 83 ms 3116 KB Output is correct
7 Correct 66 ms 3140 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 515 ms 100000 KB Output is correct
12 Correct 493 ms 101456 KB Output is correct
13 Correct 523 ms 99916 KB Output is correct
14 Correct 522 ms 99872 KB Output is correct
15 Correct 513 ms 101204 KB Output is correct
16 Correct 511 ms 101968 KB Output is correct
17 Correct 507 ms 101988 KB Output is correct
18 Correct 540 ms 101900 KB Output is correct
19 Correct 483 ms 101200 KB Output is correct
20 Correct 487 ms 101164 KB Output is correct
21 Correct 484 ms 101412 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 104208 KB Output is correct
2 Correct 92 ms 3548 KB Output is correct
3 Correct 93 ms 3664 KB Output is correct
4 Correct 91 ms 3668 KB Output is correct
5 Correct 94 ms 3680 KB Output is correct
6 Correct 93 ms 3660 KB Output is correct
7 Correct 104 ms 3784 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 608 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 644 ms 100896 KB Output is correct
12 Correct 648 ms 104424 KB Output is correct
13 Correct 670 ms 100948 KB Output is correct
14 Correct 694 ms 100804 KB Output is correct
15 Correct 664 ms 104164 KB Output is correct
16 Correct 704 ms 104276 KB Output is correct
17 Correct 664 ms 104128 KB Output is correct
18 Correct 649 ms 104276 KB Output is correct
19 Correct 714 ms 104016 KB Output is correct
20 Correct 725 ms 104016 KB Output is correct
21 Correct 650 ms 104016 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 101428 KB Output is correct
2 Correct 67 ms 3152 KB Output is correct
3 Correct 63 ms 3140 KB Output is correct
4 Correct 52 ms 2896 KB Output is correct
5 Correct 90 ms 3080 KB Output is correct
6 Correct 83 ms 3116 KB Output is correct
7 Correct 66 ms 3140 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 515 ms 100000 KB Output is correct
12 Correct 493 ms 101456 KB Output is correct
13 Correct 523 ms 99916 KB Output is correct
14 Correct 522 ms 99872 KB Output is correct
15 Correct 513 ms 101204 KB Output is correct
16 Correct 511 ms 101968 KB Output is correct
17 Correct 507 ms 101988 KB Output is correct
18 Correct 540 ms 101900 KB Output is correct
19 Correct 483 ms 101200 KB Output is correct
20 Correct 487 ms 101164 KB Output is correct
21 Correct 484 ms 101412 KB Output is correct
22 Correct 742 ms 103760 KB Output is correct
23 Correct 104 ms 3668 KB Output is correct
24 Correct 97 ms 3640 KB Output is correct
25 Correct 97 ms 3664 KB Output is correct
26 Correct 113 ms 3924 KB Output is correct
27 Correct 129 ms 3612 KB Output is correct
28 Correct 101 ms 3664 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 748 ms 100796 KB Output is correct
33 Correct 766 ms 103508 KB Output is correct
34 Correct 745 ms 100760 KB Output is correct
35 Correct 758 ms 100788 KB Output is correct
36 Correct 738 ms 100764 KB Output is correct
37 Correct 680 ms 100764 KB Output is correct
38 Correct 662 ms 100688 KB Output is correct
39 Correct 730 ms 103504 KB Output is correct
40 Correct 757 ms 103712 KB Output is correct
41 Correct 751 ms 103652 KB Output is correct
42 Correct 807 ms 103508 KB Output is correct
43 Correct 807 ms 103624 KB Output is correct
44 Correct 751 ms 103608 KB Output is correct
45 Correct 776 ms 103564 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 102808 KB Output is correct
2 Correct 83 ms 3920 KB Output is correct
3 Correct 86 ms 3464 KB Output is correct
4 Correct 85 ms 3664 KB Output is correct
5 Correct 84 ms 3660 KB Output is correct
6 Correct 87 ms 3720 KB Output is correct
7 Correct 89 ms 3664 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 464 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 537 ms 102804 KB Output is correct
12 Correct 485 ms 102736 KB Output is correct
13 Correct 486 ms 103248 KB Output is correct
14 Correct 491 ms 103440 KB Output is correct
15 Correct 489 ms 102992 KB Output is correct
16 Correct 477 ms 102948 KB Output is correct
17 Correct 469 ms 102700 KB Output is correct
18 Correct 474 ms 102736 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -