oj.uz

답안 #877221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877221 2023-11-23T03:59:27 Z The_Samurai 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 128 ms 3332 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;
    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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 448 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 10 ms 472 KB Output is correct
5 Correct 11 ms 604 KB Output is correct
6 Correct 11 ms 644 KB Output is correct
7 Correct 11 ms 600 KB Output is correct
8 Correct 29 ms 1372 KB Output is correct
9 Correct 55 ms 2444 KB Output is correct
10 Correct 54 ms 2384 KB Output is correct
11 Correct 49 ms 2636 KB Output is correct
12 Correct 53 ms 2520 KB Output is correct
13 Correct 124 ms 2896 KB Output is correct
14 Correct 128 ms 2900 KB Output is correct
15 Correct 43 ms 2896 KB Output is correct
16 Correct 44 ms 3332 KB Output is correct
17 Correct 108 ms 2896 KB Output is correct
18 Correct 108 ms 2900 KB Output is correct
19 Correct 42 ms 3156 KB Output is correct
20 Correct 43 ms 2968 KB Output is correct