Submission #1209172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209172		buzdi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	209 ms	132264 KiB

apple

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int XMAX = 1e9;

struct Node {
    int sum, left, right, lazy;
    Node() : sum(0), left(-1), right(-1), lazy(0) {}
};

struct AINT {
    int n;
    vector<Node> tree;

    AINT() {}
    AINT(int n) {
        this->n = n;
        tree.push_back(Node());
    }

    int create_node() {
        int index = tree.size();
        tree.push_back(Node());
        return index;
    }

    void apply_lazy(int node, int left, int right, int parent_lazy) {
        if(!parent_lazy) {
            return;
        }
        tree[node].sum = (right - left + 1);
        tree[node].lazy = parent_lazy;
    }

    void push_lazy(int node, int left, int right) {
        if(tree[node].left == -1) {
            tree[node].left = create_node();
        }
        if(tree[node].right == -1) {
            tree[node].right = create_node();
        }

        int mid = (left + right) / 2;
        apply_lazy(tree[node].left, left, mid, tree[node].lazy);
        apply_lazy(tree[node].right, mid + 1, right, tree[node].lazy);
        tree[node].lazy = 0;
    }

    void update(int node, int left, int right, int u_left, int u_right) {
        if(left > u_right || right < u_left) {
            return;
        }
        if(left >= u_left && right <= u_right) {
            apply_lazy(node, left, right, 1);
            return;
        }

        push_lazy(node, left, right);
        int mid = (left + right) / 2;
        update(tree[node].left, left, mid, u_left, u_right);
        update(tree[node].right, mid + 1, right, u_left, u_right);
        tree[node].sum = tree[tree[node].left].sum + tree[tree[node].right].sum;
    }
    
    int query(int node, int left, int right, int q_left, int q_right) {
        if(left > q_right || right < q_left) {
            return 0;
        }
        if(left >= q_left && right <= q_right) {
            return tree[node].sum;
        }

        push_lazy(node, left, right);
        int mid = (left + right) / 2;
        return query(tree[node].left, left, mid, q_left, q_right) + query(tree[node].right, mid + 1, right, q_left, q_right);
    }
}aint;

int n, answer;

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

    cin >> n;
    aint = AINT(XMAX);
    for(int i = 1; i <= n; i++) {
        int type, x, y;
        cin >> type >> x >> y;
        x += answer;
        y += answer;
        if(type == 1) {
            answer = aint.query(0, 1, XMAX, x, y);
            cout << answer << '\n';
        }
        else {
            aint.update(0, 1, XMAX, x, y);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100