Submission #1188636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188636		sonya	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	267 ms	148648 KiB

apple

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int cl = 0, cr = 0;
    long long sum = 0;
    bool lazy = false; // дали целият интервал е маркиран като червен
};

vector<Node> tree(2);
int next_node = 2;
const int MAX = 1e9;

void create(int h) {
    if (tree[h].cl == 0) {
        tree[h].cl = next_node++;
        tree[h].cr = next_node++;
        if ((int)tree.size() <= next_node + 5)
            tree.resize(next_node + 10);
    }
}

void push(int node, int l, int r) {
    if (!tree[node].lazy) return;

    create(node);
    int mid = (l + r) / 2;

    // Постави lazy на децата
    tree[tree[node].cl].lazy = true;
    tree[tree[node].cl].sum = mid - l + 1;

    tree[tree[node].cr].lazy = true;
    tree[tree[node].cr].sum = r - mid;

    // Премахни lazy от текущия
    tree[node].lazy = false;
}

void update(int node, int l, int r, int ul, int ur) {
    if (r < ul || l > ur) return;
    if (ul <= l && r <= ur) {
        tree[node].lazy = true;
        tree[node].sum = r - l + 1;
        return;
    }

    push(node, l, r);
    create(node);

    int mid = (l + r) / 2;
    update(tree[node].cl, l, mid, ul, ur);
    update(tree[node].cr, mid + 1, r, ul, ur);
    tree[node].sum = tree[tree[node].cl].sum + tree[tree[node].cr].sum;
}

long long query(int node, int l, int r, int ql, int qr) {
    if (r < ql || l > qr || node == 0) return 0;
    if (ql <= l && r <= qr) return tree[node].sum;

    push(node, l, r);
    create(node);

    int mid = (l + r) / 2;
    return query(tree[node].cl, l, mid, ql, qr) +
           query(tree[node].cr, mid + 1, r, ql, qr);
}

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

    int M;
    cin >> M;
    long long C = 0;

    for (int i = 0; i < M; ++i) {
        int D, X, Y;
        cin >> D >> X >> Y;

        long long l = X + C;
        long long r = Y + C;
        if (l > r) swap(l, r);

        l = max(1LL, min(l, (long long)MAX));
        r = max(1LL, min(r, (long long)MAX));

        if (D == 1) {
            long long res = query(1, 1, MAX, l, r);
            cout << res << '\n';
            C = res;
        } else {
            update(1, 1, MAX, l, r);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100