답안 #1115668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115668	2024-11-20T18:31:00 Z	vanea	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	317 ms	202268 KB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    int sum = 0, lazy = 0;
    int l, r;
    int left_child = -1, right_child = -1;
    Node(int lb, int rb) {
        l = lb;
        r = rb;
    }
};

int n, cnt = 0;

vector<Node> tree;

void extend_left(int curr) {
    if(tree[curr].left_child == -1 && tree[curr].l < tree[curr].r) {
        int mid = (tree[curr].l+tree[curr].r)/2;
        tree[curr].left_child = ++cnt;
        tree.push_back(Node(tree[curr].l, mid));
    }
}

void extend_right(int curr) {
    if(tree[curr].right_child == -1 && tree[curr].l < tree[curr].r) {
        int mid = (tree[curr].l+tree[curr].r)/2;
        tree[curr].right_child = ++cnt;
        tree.push_back(Node(mid+1, tree[curr].r));
    }
}

void propagate(int curr) {
    if(tree[curr].l == tree[curr].r) return ;
    if(tree[curr].lazy == 0) return ;
    int mid = (tree[curr].r+tree[curr].l)/2;
    tree[tree[curr].left_child].lazy = 1;
    tree[tree[curr].left_child].sum = (mid-tree[curr].l+1);
    tree[tree[curr].right_child].lazy = 1;
    tree[tree[curr].right_child].sum = (tree[curr].r-mid);
    tree[curr].lazy = 0;
}

void upd(int l, int r, int curr) {
    if(l <= tree[curr].l && tree[curr].r <= r) {
        tree[curr].lazy = 1;
        tree[curr].sum = (tree[curr].r-tree[curr].l+1);
        return ;
    }
    if(l > tree[curr].r || r < tree[curr].l) return ;
    extend_left(curr);
    extend_right(curr);
    propagate(curr);
    upd(l, r, tree[curr].left_child);
    upd(l, r, tree[curr].right_child);
    tree[curr].sum = tree[tree[curr].left_child].sum+tree[tree[curr].right_child].sum;
}

int query(int l, int r, int curr) {
    if(l <= tree[curr].l && tree[curr].r <= r) return tree[curr].sum;
    if(l > tree[curr].r || r < tree[curr].l) return 0;
    extend_left(curr);
    extend_right(curr);
    propagate(curr);
    return query(l, r, tree[curr].left_child) +
    query(l, r, tree[curr].right_child);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> q;
    //tree.reserve(2 * q * __lg(n));
    tree.push_back(Node(0, 1e9+1));
    int c = 0;
    while(q--) {
        int flag;
        cin >> flag;
        if(flag == 1) {
            int l, r;
            cin >> l >> r;
            l += c; r += c;
            c = query(l, r, 0);
            cout << c << '\n';
        }
        else {
            int l, r;
            cin >> l >> r;
            l += c; r += c;
            upd(l, r, 0);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	12 ms	4292 KB	Output is correct
5	Correct	15 ms	4292 KB	Output is correct
6	Correct	14 ms	4308 KB	Output is correct
7	Correct	14 ms	4292 KB	Output is correct
8	Correct	80 ms	27868 KB	Output is correct
9	Correct	170 ms	53144 KB	Output is correct
10	Correct	162 ms	52896 KB	Output is correct
11	Correct	198 ms	52892 KB	Output is correct
12	Correct	183 ms	52896 KB	Output is correct
13	Correct	167 ms	103572 KB	Output is correct
14	Correct	173 ms	103584 KB	Output is correct
15	Correct	317 ms	200076 KB	Output is correct
16	Correct	295 ms	202268 KB	Output is correct
17	Correct	173 ms	103572 KB	Output is correct
18	Correct	169 ms	103552 KB	Output is correct
19	Correct	296 ms	199996 KB	Output is correct
20	Correct	300 ms	200220 KB	Output is correct