답안 #876638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876638	2023-11-22T06:31:04 Z	The_Samurai	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	10 ms	632 KB

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;
    arr[0] = 0;
    if (arr[1]) arr[0] += get_sum(l, r, arr[1], lx, m);
    if (arr[2]) arr[0] += get_sum(l, r, arr[2], m, rx);
    return arr[0];
}

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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Incorrect	10 ms	632 KB	Output isn't correct
5	Halted	0 ms	0 KB	-