답안 #343085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343085 2021-01-03T12:07:24 Z apostoldaniel854 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
423 ms 167468 KB
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

struct DynamicSegTree {
    struct Node {
        int left_node;
        int right_node;
        int sum;
        bool lazy;
        int sz;
    };
    int tag = 0;
    int n;
    vector <Node> seg;
    DynamicSegTree (int n) {
        this->n = n;
        seg.pb ({0, 0, 0, 0, 0});
        seg.pb ({0, 0, 0, 0, n});
        tag++;
    }
    void push (int node) {
        if (seg[node].lazy) {
            int left_node = seg[node].left_node;
            int right_node = seg[node].right_node;
            seg[left_node].sum = seg[left_node].sz;
            seg[right_node].sum = seg[right_node].sz;
            seg[left_node].lazy = true;
            seg[right_node].lazy = true;
            seg[node].lazy = false;
        }
    }
    void update (int node, int lb, int rb, int q_left, int q_right) {
        if (q_left <= lb && rb <= q_right) {
            seg[node].lazy = true;
            seg[node].sum = seg[node].sz;
            return;
        }
        int mid = (lb + rb) / 2;
        if (not seg[node].left_node) {
            seg[node].left_node = ++tag;
            seg.push_back ({0, 0, 0, 0, mid - lb + 1});
        }
        if (not seg[node].right_node) {
            seg[node].right_node = ++tag;
            seg.push_back ({0, 0, 0, 0, rb - mid});
        }
        push (node);
        if (q_left <= mid)
            update (seg[node].left_node, lb, mid, q_left, q_right);
        if (q_right >= mid + 1)
            update (seg[node].right_node, mid + 1, rb, q_left, q_right);
        seg[node].sum = seg[seg[node].left_node].sum + seg[seg[node].right_node].sum;
    }
    int query (int node, int lb, int rb, int q_left, int q_right) {
        if (q_left <= lb && rb <= q_right)
            return seg[node].sum;
        int mid = (lb + rb) / 2;
        if (not seg[node].left_node) {
            seg[node].left_node = ++tag;
            seg.push_back ({0, 0, 0, 0, mid - lb + 1});
        }
        if (not seg[node].right_node) {
            seg[node].right_node = ++tag;
            seg.push_back ({0, 0, 0, 0, rb - mid});
        }
        push (node);
        int ans = 0;
        if (q_left <= mid)
            ans += query (seg[node].left_node, lb, mid, q_left, q_right);
        if (q_right >= mid + 1)
            ans += query (seg[node].right_node, mid + 1, rb, q_left, q_right);
        return ans;
    }
};

const int MX = 1e9;

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


    int q;
    cin >> q;
    DynamicSegTree my_seg (MX);
    int c = 0;
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        x += c, y += c;
        assert (1 <= x && x <= MX && 1 <= y && y <= MX);
        if (type == 1)
            cout << (c = my_seg.query (1, 1, MX, x, y)) << "\n";
        else
            my_seg.update (1, 1, MX, x, y);
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 13 ms 3168 KB Output is correct
5 Correct 16 ms 3296 KB Output is correct
6 Correct 16 ms 3168 KB Output is correct
7 Correct 18 ms 3296 KB Output is correct
8 Correct 116 ms 21700 KB Output is correct
9 Correct 252 ms 42924 KB Output is correct
10 Correct 254 ms 42668 KB Output is correct
11 Correct 268 ms 42836 KB Output is correct
12 Correct 260 ms 42800 KB Output is correct
13 Correct 271 ms 84992 KB Output is correct
14 Correct 273 ms 85120 KB Output is correct
15 Correct 423 ms 167340 KB Output is correct
16 Correct 410 ms 167388 KB Output is correct
17 Correct 275 ms 84992 KB Output is correct
18 Correct 274 ms 85120 KB Output is correct
19 Correct 417 ms 167340 KB Output is correct
20 Correct 423 ms 167468 KB Output is correct