Submission #1243337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243337		lorebas12	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	425 ms	263448 KiB

apple

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

#define int long long

const int MAX_RANGE = 1e9;

struct Node {
    int sum = 0, lazy = 0;
    int left = -1, right = -1;
};

vector<Node> seg(1);  // nó 0 é a raiz
int C = 0;  // valor acumulado da query anterior

int create_node() {
    seg.push_back(Node());
    return seg.size() - 1;
}

void push(int u, int l, int r) {
    if (seg[u].lazy == 0) return;

    // Aplica o lazy no nó atual
    seg[u].sum = (r - l + 1); // marcar tudo como maduro
    if (l != r) {
        if (seg[u].left == -1) seg[u].left = create_node();
        if (seg[u].right == -1) seg[u].right = create_node();
        seg[seg[u].left].lazy = 1;
        seg[seg[u].right].lazy = 1;
    }
    seg[u].lazy = 0;
}

void update(int u, int l, int r, int ql, int qr) {
    push(u, l, r);
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[u].lazy = 1;
        push(u, l, r);
        return;
    }

    int m = (l + r) / 2;
    if (seg[u].left == -1) seg[u].left = create_node();
    if (seg[u].right == -1) seg[u].right = create_node();

    update(seg[u].left, l, m, ql, qr);
    update(seg[u].right, m + 1, r, ql, qr);

    seg[u].sum = seg[seg[u].left].sum + seg[seg[u].right].sum;
}

int query(int u, int l, int r, int ql, int qr) {
    if (u == -1 || qr < l || r < ql) return 0;
    push(u, l, r);
    if (ql <= l && r <= qr) return seg[u].sum;

    int m = (l + r) / 2;
    int sl = query(seg[u].left, l, m, ql, qr);
    int sr = query(seg[u].right, m + 1, r, ql, qr);
    return sl + sr;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;
    cin >> M;

    while (M--) {
        int D, X, Y;
        cin >> D >> X >> Y;
        X += C;
        Y += C;

        if (D == 1) {
            int ans = query(0, 1, MAX_RANGE, X, Y);
            cout << ans << '\n';
            C = ans;
        } else {
            update(0, 1, MAX_RANGE, X, Y);
        }
    }
}

• Subtask 1: 0 / 100