Submission #1243336

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

apple

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

#define int long long

const int MAX_NODES = 4e7;  // Máximo de nós
const int MAX_RANGE = 1e9;  // Maior coordenada possível

struct Node {
    int sum = 0;  // Quantas árvores estão maduras neste nó
    int left = -1, right = -1;  // Índices dos filhos
};

vector<Node> seg(1);  // Começa com nó raiz em índice 0
int C = 0;  // Valor acumulado usado nos deslocamentos

// Atualiza intervalo [l, r] com valor 1 (madura)
void update(int u, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
        seg[u].sum = tr - tl + 1;
        return;
    }
    int tm = (tl + tr) / 2;
    if (seg[u].left == -1) {
        seg[u].left = seg.size();
        seg.emplace_back();
    }
    if (seg[u].right == -1) {
        seg[u].right = seg.size();
        seg.emplace_back();
    }
    update(seg[u].left, tl, tm, l, r);
    update(seg[u].right, tm + 1, tr, l, r);
    seg[u].sum = (seg[u].left == -1 ? 0 : seg[seg[u].left].sum) + 
                 (seg[u].right == -1 ? 0 : seg[seg[u].right].sum);
}

// Consulta quantas árvores maduras estão em [l, r]
int query(int u, int tl, int tr, int l, int r) {
    if (u == -1 || r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return seg[u].sum;
    int tm = (tl + tr) / 2;
    int sl = query(seg[u].left, tl, tm, l, r);
    int sr = query(seg[u].right, tm + 1, tr, l, r);
    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) {  // Chris chega
            int res = query(0, 1, MAX_RANGE, X, Y);
            cout << res << '\n';
            C = res;
        } else {  // Maturação de maçãs
            update(0, 1, MAX_RANGE, X, Y);
        }
    }
}

• Subtask 1: 0 / 100