Submission #877221

#	Time	Username	Problem	Language	Result	Execution time	Memory
877221		The_Samurai	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	128 ms	3332 KiB

apple

// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const ll inf = 1e18;
const int N = 1 << 30;

int z = 2;
map<int, array<int, 4>> tree;
// val - 0, left_child - 1, right_child - 2, lazy - 3

void propagate(array<int, 4> &arr, int lx, int rx) {
    int m = (lx + rx) >> 1;
    if (arr[3]) {
        if (arr[1]) {
            tree[arr[1]][0] = m - lx;
            tree[arr[1]][3] = true;
        }
        if (arr[2]) {
            tree[arr[2]][0] = rx - m;
            tree[arr[2]][3] = true;
        }
    }
}

void update(int l, int r, int x, int lx, int rx) {
    if (l >= rx or lx >= r) return;
    auto &arr = tree[x];
    if (arr[3]) return;
    if (l <= lx and rx <= r) {
        arr[0] = rx - lx;
        arr[3] = true;
        return;
    }
    if (arr[1] == 0) arr[1] = z++;
    if (arr[2] == 0) arr[2] = z++;

    int m = (lx + rx) >> 1;
    update(l, r, arr[1], lx, m);
    update(l, r, arr[2],m, rx);

    arr[0] = tree[arr[1]][0] + tree[arr[2]][0];
}

int get_sum(int l, int r, int x, int lx, int rx) {
//    cout << l << ' ' << r << ' ' << x << ' ' << lx << ' ' << rx << ' ' << tree[x][0] << endl;
    if (l >= rx or lx >= r) return 0;
    if (l <= lx and rx <= r) return tree[x][0];
    auto &arr = tree[x];
    if (arr[3]) return min(rx, r) - max(lx, l);
    int m = (lx + rx) >> 1;
    int sum = 0;
    if (arr[1]) sum += get_sum(l, r, arr[1], lx, m);
    if (arr[2]) sum += get_sum(l, r, arr[2], m, rx);
    return sum;
}

void solve() {
    int q, c = 0;
    cin >> q;
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        l += c; r += c;
        if (op == 1) {
            c = get_sum(l, r + 1, 1, 0, N);
            cout << c << '\n';
        } else {
            update(l, r + 1, 1, 0, N);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

• Subtask 1: 100 / 100