Submission #1267558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267558		i_elhdad	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	1 ms	320 KiB

apple

// compile: g++ -O2 -std=c++17 apple.cpp -o apple
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int ST_L = 1;
const int ST_R = 1000000000;
const int MAXNODES = 4000000; // adjust if you know you'll need more (4e6 is usually safe)

static int Lch[MAXNODES];
static int Rch[MAXNODES];
static int val[MAXNODES];
static unsigned char lazy[MAXNODES]; // 0 or 1
static int nodes = 1; // 0 is Empty sentinel, start allocating from 1

inline int new_node() {
    if (nodes >= MAXNODES) {
        // should not happen under normal constraints; if it does, increase MAXNODES
        fprintf(stderr, "OUT OF NODES\n");
        exit(1);
    }
    Lch[nodes] = 0;
    Rch[nodes] = 0;
    val[nodes] = 0;
    lazy[nodes] = 0;
    return nodes++;
}

void propagate(int &id, int st, int en) {
    if (id == 0) return;
    if (!lazy[id]) return;
    val[id] = en - st + 1;
    if (st != en) {
        if (Lch[id] == 0) Lch[id] = new_node();
        if (Rch[id] == 0) Rch[id] = new_node();
        lazy[Lch[id]] = 1;
        lazy[Rch[id]] = 1;
    }
    lazy[id] = 0;
}

void add_range(int l, int r, int &id, int st = ST_L, int en = ST_R) {
    if (l > r) return;
    if (r < st || l > en) return;
    if (id == 0) id = new_node();
    propagate(id, st, en);
    if (l <= st && en <= r) {
        lazy[id] = 1;
        propagate(id, st, en);
        return;
    }
    int mid = st + (en - st) / 2;
    add_range(l, r, Lch[id], st, mid);
    add_range(l, r, Rch[id], mid + 1, en);
    int lv = (Lch[id] ? val[Lch[id]] : 0);
    int rv = (Rch[id] ? val[Rch[id]] : 0);
    val[id] = lv + rv;
}

int query_range(int l, int r, int id, int st = ST_L, int en = ST_R) {
    if (l > r) return 0;
    if (id == 0) return 0;
    if (r < st || l > en) return 0;
    propagate(id, st, en);
    if (l <= st && en <= r) return val[id];
    int mid = st + (en - st) / 2;
    return query_range(l, r, Lch[id], st, mid) + query_range(l, r, Rch[id], mid + 1, en);
}

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

    // If you must use files (problem states f.in/f.out), check return values to avoid warnings:
    if (!freopen("f.in", "r", stdin)) {
        // If file not found, we continue reading from stdin (useful for online judge).
        // But print warning to stderr so you notice during local testing.
        // Comment out the exit if you want fall-back to stdin.
        // perror("f.in");
        // exit(1);
    }
    if (!freopen("f.out", "w", stdout)) {
        // perror("f.out");
        // exit(1);
    }

    int M;
    if (!(cin >> M)) return 0;
    int root = 0; // 0 means Empty
    int C = 0;
    for (int i = 0; i < M; ++i) {
        int D, X, Y;
        cin >> D >> X >> Y;
        ll l = (ll)X + C;
        ll r = (ll)Y + C;
        if (l > r) swap(l, r);
        if (l < ST_L) l = ST_L;
        if (r > ST_R) r = ST_R;
        if (D == 2) {
            add_range((int)l, (int)r, root);
        } else {
            C = query_range((int)l, (int)r, root);
            cout << C << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 100