oj.uz

답안 #876676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876676 2023-11-22T08:05:31 Z The_Samurai 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 10 ms 504 KB 
// 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;
    propagate(arr, lx, rx);
    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 0 ms 348 KB Output is correct
4 Incorrect 10 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -