Submission #1252392

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

apple

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

const int MAX_NODES = 4000000;
const int L = 1;
const int R = 1000000000;

vector<int> leftChild, rightChild, val, lazy;

int nodeCount = 1; 
void init() {
    leftChild.assign(MAX_NODES, 0);
    rightChild.assign(MAX_NODES, 0);
    val.assign(MAX_NODES, 0);
    lazy.assign(MAX_NODES, 0);
}


int newNode() {
    return ++nodeCount;
}

void push(int idx, int l, int r) {
    if (lazy[idx] == 0) return;
    val[idx] = r - l + 1; 
    if (l != r) {
        if (leftChild[idx] == 0) leftChild[idx] = newNode();
        if (rightChild[idx] == 0) rightChild[idx] = newNode();

        lazy[leftChild[idx]] = 1;
        lazy[rightChild[idx]] = 1;
    }
    lazy[idx] = 0;
}

void update(int idx, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return;
    if (idx == 0) return; 

    if (idx == 1 && val.size() < nodeCount + 10) {
    }

    if (ql <= l && r <= qr) {
        lazy[idx] = 1;
        push(idx, l, r);
        return;
    }
    push(idx, l, r);

    int mid = (l + r) >> 1;
    if (ql <= mid) {
        if (leftChild[idx] == 0) leftChild[idx] = newNode();
        update(leftChild[idx], l, mid, ql, qr);
    }
    if (qr > mid) {
        if (rightChild[idx] == 0) rightChild[idx] = newNode();
        update(rightChild[idx], mid + 1, r, ql, qr);
    }
    val[idx] = 0;
    if (leftChild[idx] != 0) val[idx] += val[leftChild[idx]];
    if (rightChild[idx] != 0) val[idx] += val[rightChild[idx]];
}

int query(int idx, int l, int r, int ql, int qr) {
    if (idx == 0 || r < ql || l > qr) return 0;
    push(idx, l, r);
    if (ql <= l && r <= qr) return val[idx];
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res += query(leftChild[idx], l, mid, ql, qr);
    if (qr > mid) res += query(rightChild[idx], mid + 1, r, ql, qr);
    return res;
}

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

    init();

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

    nodeCount = 1;

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

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

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

• Subtask 1: 0 / 100