답안 #800795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
800795 2023-08-01T20:57:45 Z atom 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
217 ms 190940 KB
#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();
    }
}
# 결과 실행 시간 메모리 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