Submission #800795

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
800795	2023-08-01T20:57:45 Z	atom	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	217 ms	190940 KB

apple

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, b) for(int i = 0; i < b; i++)
#define PER(i, b) for(int i = b - 1; i >= 0; i--)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#ifdef JASPER2
#include "debug.h"
#else
#define debug(...) 166
#endif

using pii = pair < int, int >;
const ll LINF = 1e18 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;

struct Node {
    int val, lzy, l, r;
    Node() : val(0), lzy(0), l(-1), r(-1) {};
};

struct SparseSegmentTree {

    vector <Node> f;
    int n;

    SparseSegmentTree() : f(MAX * 60) , n(1) {};

    void push(int x, int l, int r) {
        if (!f[x].lzy)
            return;
        if (f[x].l == -1)
            f[x].l = ++n;
        if (f[x].r == -1)
            f[x].r = ++n;

        int m = (l + r) >> 1;
        f[f[x].l].lzy = f[x].lzy;
        f[f[x].r].lzy = f[x].lzy;
        f[f[x].l].val = f[x].lzy * (m - l + 1);
        f[f[x].r].val = f[x].lzy * (r - m);
        f[x].lzy = 0;
    }

    void upd(int u, int v, int val, int x = 1, int l = 1, int r = INF) {
        if (l > v || r < u)
            return;
        if (u <= l && r <= v) {
            f[x].val = val * (r - l + 1);
            f[x].lzy = val;
            return;
        }

        if (f[x].l == -1)
            f[x].l = ++n;
        if (f[x].r == -1)
            f[x].r = ++n;
        push(x, l, r);

        int m = (l + r) >> 1;
        upd(u, v, val, f[x].l, l, m);
        upd(u, v, val, f[x].r, m + 1, r);
        f[x].val = f[f[x].l].val + f[f[x].r].val;
    }

    int qry(int u, int v, int x = 1, int l = 1, int r = INF) {
        if (l > v || r < u)
            return 0;
        if (u <= l && r <= v)
            return f[x].val;

        if (f[x].l == -1)
            f[x].l = ++n;
        if (f[x].r == -1)
            f[x].r = ++n;
        push(x, l, r);

        int m = (l + r) >> 1;
        int ql = qry(u, v, f[x].l, l, m);
        int qr = qry(u, v, f[x].r, m + 1, r);
        return (ql + qr);
    }
};




void run_case() {
    int q;
    SparseSegmentTree st;
    cin >> q;
    int c = 0;
    while (q--) {
        int cmd, x, y;
        cin >> cmd >> x >> y;
//        debug(cmd, x, y);
        if (cmd == 1) {
            c = st.qry(x + c , y + c);
            cout << c << "\n";
        }
        else
            st.upd(x + c, y + c, 1);
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    #ifdef JASPER2
        freopen("in1", "r", stdin);
    #endif

    int Test = 1;
    //cin >> Test;
    for (int test = 1; test <= Test; test++){

        run_case();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	188148 KB	Output is correct
2	Correct	72 ms	188076 KB	Output is correct
3	Correct	72 ms	188208 KB	Output is correct
4	Correct	77 ms	188108 KB	Output is correct
5	Correct	80 ms	188144 KB	Output is correct
6	Correct	78 ms	188184 KB	Output is correct
7	Correct	77 ms	188220 KB	Output is correct
8	Correct	117 ms	188376 KB	Output is correct
9	Correct	184 ms	188544 KB	Output is correct
10	Correct	174 ms	188548 KB	Output is correct
11	Correct	176 ms	188552 KB	Output is correct
12	Correct	185 ms	188720 KB	Output is correct
13	Correct	167 ms	188656 KB	Output is correct
14	Correct	173 ms	188624 KB	Output is correct
15	Correct	210 ms	188572 KB	Output is correct
16	Correct	211 ms	190760 KB	Output is correct
17	Correct	170 ms	190668 KB	Output is correct
18	Correct	169 ms	190764 KB	Output is correct
19	Correct	217 ms	190940 KB	Output is correct
20	Correct	206 ms	190796 KB	Output is correct