Submission #343085

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343085	2021-01-03T12:07:24 Z	apostoldaniel854	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	423 ms	167468 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	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