Submission #1252372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252372		hossainrasel1042	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	386 ms	290336 KiB

apple

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

const int L = 1;
const int R = 1e9;

struct Node {
    Node *l, *r;
    int val, lazy;
    Node() : l(nullptr), r(nullptr), val(0), lazy(0) {}
};

void push(Node*& root, int l, int r) {
    if (!root || root->lazy == 0) return;
    root->val = (r - l + 1);
    if (l != r) {
        int mid = (l + r) >> 1;
        if (!root->l) root->l = new Node();
        if (!root->r) root->r = new Node();
        root->l->val = mid - l + 1;
        root->r->val = r - mid;
        root->l->lazy = 1;
        root->r->lazy = 1;
    }
    root->lazy = 0;
}

void update(Node*& root, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return;
    if (!root) root = new Node();
    push(root, l, r);
    if (l >= ql && r <= qr) {
        root->lazy = 1;
        push(root, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(root->l, l, mid, ql, qr);
    update(root->r, mid + 1, r, ql, qr);
    root->val = (root->l ? root->l->val : 0) + (root->r ? root->r->val : 0);
}

int query(Node*& root, int l, int r, int ql, int qr) {
    if (!root || r < ql || l > qr) return 0;
    push(root, l, r);
    if (l >= ql && r <= qr) return root->val;
    int mid = (l + r) >> 1;
    return query(root->l, l, mid, ql, qr) + query(root->r, mid + 1, r, ql, qr);
}

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

    int M;
    cin >> M;

    int C = 0;
    Node* root = nullptr;

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

        // Clamp interval inside valid range
        ql = max(ql, L);
        qr = min(qr, R);

        if (ql > qr) {
            if (D == 1) {
                C = 0;
                cout << C << '\n';
            }
            continue;
        }

        if (D == 1) {
            C = query(root, L, R, ql, qr);
            cout << C << '\n';
        } else {
            update(root, L, R, ql, qr);
        }
    }

    return 0;
}

• Subtask 1: 0 / 100