oj.uz

Submission #892538

# Submission time Handle Problem Language Result Execution time Memory
892538 2023-12-25T13:21:49 Z CDuong Progression (NOI20_progression) C++17
57 / 100
 504 ms 99352 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

struct SegmentTree {
    struct node {
        i64 val = 0;
        int same = 0, len = 0;
        pair<int, int> pfx, sfx;
        i64 lz_mul = 1, lz_add = 0;

        node() {}
        node(int val) : val(val), same(1), len(1), pfx({val, 1}), sfx({val, 1}) {}
        
        node operator + (const node &rhs) {
            node res;
            res.val = val + rhs.val;
            res.len = len + rhs.len;
            res.same = max(same, rhs.same);
            if (sfx.ff == rhs.pfx.ff) res.same = max(res.same, sfx.ss + rhs.pfx.ss);
            res.pfx = pfx, res.sfx = rhs.sfx;
            if (pfx.ss == len and pfx.ff == rhs.pfx.ff) res.pfx = {pfx.ff, pfx.ss + rhs.pfx.ss};
            if (rhs.sfx.ss == rhs.len and sfx.ff == rhs.sfx.ff) res.sfx = {rhs.sfx.ff, rhs.sfx.ss + sfx.ss};
            // cout << *this << endl << rhs << endl << res << endl << endl;
            return res;
        }

        friend ostream & operator << (ostream &out, node o) {
            return out << o.pfx.ff << " " << o.pfx.ss << " " << o.sfx.ff << " " << o.sfx.ss << " " << o.same;
        }
    };

    int n;
    vector<node> data;

    SegmentTree(int n, vector<int> &diff) : n(n), data(4 * n + 10) {
        auto build = [&](auto build, int l, int r, int idx) -> void {
            if (l == r) {
                data[idx] = node(diff[l]);
                return;
            }
            int mid = (l + r) >> 1;
            build(build, l, mid, idx << 1);
            build(build, mid + 1, r, idx << 1 | 1);
            data[idx] = data[idx << 1] + data[idx << 1 | 1];
        };
        build(build, 1, n, 1);
    };

    void apply(int idx, i64 mul, i64 add) {
        if (mul == 0) {
            data[idx].val = add * data[idx].len;
            data[idx].same = data[idx].len;
            data[idx].pfx = data[idx].sfx = {add, data[idx].len};
            data[idx].lz_mul = mul, data[idx].lz_add = add;
        }
        else {
            data[idx].val += add * data[idx].len;
            data[idx].pfx.ff += add, data[idx].sfx.ff += add;
            data[idx].lz_add += add;
        }
    }

    void down(int idx) {
        apply(idx << 1, data[idx].lz_mul, data[idx].lz_add);
        apply(idx << 1 | 1, data[idx].lz_mul, data[idx].lz_add);
        data[idx].lz_add = 0, data[idx].lz_mul = 1;
    }

    void update(int l, int r, int idx, int u, int v, i64 mul, i64 add) {
        if (u <= l && r <= v) {
            apply(idx, mul, add);
            return;
        }
        down(idx);
        int mid = (l + r) >> 1;
        if (u <= mid) update(l, mid, idx << 1, u, v, mul, add);
        if (mid + 1 <= v) update(mid + 1, r, idx << 1 | 1, u, v, mul, add);
        data[idx] = data[idx << 1] + data[idx << 1 | 1];
    }

    void update(int u, int v, i64 mul, i64 add) {
        update(1, n, 1, u, v, mul, add);
    }

    node get(int l, int r, int idx, int u, int v) {
        if (u <= l && r <= v) return data[idx];
        down(idx);
        int mid = (l + r) >> 1;
        if (v <= mid) return get(l, mid, idx << 1, u, v);
        if (mid + 1 <= u) return get(mid + 1, r, idx << 1 | 1, u, v);
        return get(l, mid, idx << 1, u, v) + get(mid + 1, r, idx << 1 | 1, u, v);
    }

    node get(int u, int v) {
        return get(1, n, 1, u, v);
    }
};

int n, q;
int a[mxN];
vector<int> diff;

void solve() {
    cin >> n >> q;
    diff.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1];
    }
    SegmentTree st(n, diff);
    // cout << st.data[1].same << endl;
    while (q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            st.update(l, l, 1, s);
            if (l < r) st.update(l + 1, r, 1, c);
            if (r + 1 <= n) st.update(r + 1, r + 1, 1, -(1ll * c * (r - l) + s));
        }
        else if (tp == 2) {
            int l, r, s, c;
            cin >> l >> r >> s >> c;
            i64 cl = st.get(1, l).val;
            i64 cr = st.get(1, l).val;
            st.update(l, l, 1, s - cl);
            if (r + 1 <= n) st.update(r + 1, r + 1, 1, s + (r - l) * c - cr);
            if (l < r) st.update(l + 1, r, 0, c);
        }
        else {
            int l, r;
            cin >> l >> r;
            if (l == r) cout << 1 << "\n";
            else cout << st.get(l + 1, r).same + 1 << "\n";
        }
    }
    // for (int i = 1; i <= n; ++i)
    //     cout << st.get(i, i).val << " \n"[i == n];
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 98276 KB Output is correct
2 Correct 99 ms 3848 KB Output is correct
3 Correct 102 ms 3668 KB Output is correct
4 Correct 98 ms 3444 KB Output is correct
5 Correct 101 ms 3668 KB Output is correct
6 Correct 101 ms 3668 KB Output is correct
7 Correct 99 ms 3612 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 276 ms 98300 KB Output is correct
12 Correct 279 ms 98396 KB Output is correct
13 Correct 275 ms 98384 KB Output is correct
14 Correct 285 ms 98796 KB Output is correct
15 Correct 276 ms 98388 KB Output is correct
16 Correct 274 ms 98256 KB Output is correct
17 Correct 272 ms 98140 KB Output is correct
18 Correct 271 ms 98212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 348 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 203 ms 96648 KB Output is correct
2 Correct 68 ms 2932 KB Output is correct
3 Correct 63 ms 3152 KB Output is correct
4 Correct 57 ms 2900 KB Output is correct
5 Correct 70 ms 3156 KB Output is correct
6 Correct 70 ms 3152 KB Output is correct
7 Correct 70 ms 3072 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 238 ms 95260 KB Output is correct
12 Correct 204 ms 96728 KB Output is correct
13 Correct 246 ms 95276 KB Output is correct
14 Correct 240 ms 95312 KB Output is correct
15 Correct 199 ms 96500 KB Output is correct
16 Correct 255 ms 97252 KB Output is correct
17 Correct 243 ms 97104 KB Output is correct
18 Correct 257 ms 97328 KB Output is correct
19 Correct 214 ms 96724 KB Output is correct
20 Correct 224 ms 96616 KB Output is correct
21 Correct 235 ms 96552 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 99352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 96648 KB Output is correct
2 Correct 68 ms 2932 KB Output is correct
3 Correct 63 ms 3152 KB Output is correct
4 Correct 57 ms 2900 KB Output is correct
5 Correct 70 ms 3156 KB Output is correct
6 Correct 70 ms 3152 KB Output is correct
7 Correct 70 ms 3072 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 238 ms 95260 KB Output is correct
12 Correct 204 ms 96728 KB Output is correct
13 Correct 246 ms 95276 KB Output is correct
14 Correct 240 ms 95312 KB Output is correct
15 Correct 199 ms 96500 KB Output is correct
16 Correct 255 ms 97252 KB Output is correct
17 Correct 243 ms 97104 KB Output is correct
18 Correct 257 ms 97328 KB Output is correct
19 Correct 214 ms 96724 KB Output is correct
20 Correct 224 ms 96616 KB Output is correct
21 Correct 235 ms 96552 KB Output is correct
22 Correct 469 ms 98884 KB Output is correct
23 Correct 102 ms 3840 KB Output is correct
24 Correct 95 ms 3668 KB Output is correct
25 Correct 95 ms 3548 KB Output is correct
26 Correct 98 ms 3664 KB Output is correct
27 Correct 98 ms 3664 KB Output is correct
28 Correct 98 ms 3668 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 479 ms 96220 KB Output is correct
33 Correct 457 ms 98896 KB Output is correct
34 Correct 489 ms 96096 KB Output is correct
35 Correct 469 ms 96004 KB Output is correct
36 Correct 378 ms 95828 KB Output is correct
37 Correct 383 ms 96084 KB Output is correct
38 Correct 383 ms 95956 KB Output is correct
39 Correct 468 ms 98912 KB Output is correct
40 Correct 479 ms 99156 KB Output is correct
41 Correct 504 ms 98900 KB Output is correct
42 Correct 484 ms 98916 KB Output is correct
43 Correct 459 ms 98900 KB Output is correct
44 Correct 455 ms 98796 KB Output is correct
45 Correct 462 ms 99184 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 98276 KB Output is correct
2 Correct 99 ms 3848 KB Output is correct
3 Correct 102 ms 3668 KB Output is correct
4 Correct 98 ms 3444 KB Output is correct
5 Correct 101 ms 3668 KB Output is correct
6 Correct 101 ms 3668 KB Output is correct
7 Correct 99 ms 3612 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 276 ms 98300 KB Output is correct
12 Correct 279 ms 98396 KB Output is correct
13 Correct 275 ms 98384 KB Output is correct
14 Correct 285 ms 98796 KB Output is correct
15 Correct 276 ms 98388 KB Output is correct
16 Correct 274 ms 98256 KB Output is correct
17 Correct 272 ms 98140 KB Output is correct
18 Correct 271 ms 98212 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -