제출 #343085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343085		apostoldaniel854	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	423 ms	167468 KiB

apple

#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;
}

• Subtask 1: 100 / 100