답안 #550677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
550677 2022-04-18T19:35:35 Z Vladth11 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
45 ms 2964 KB
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 100001;
const ll VMAX = 1000000001;
const ll INF = (1LL << 55);
const ll MOD = 1000007;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

struct node {
    int l, r;
    int sum;
    void init() {
        l = r = -1;
        sum = 0;
    }
} aint[NMAX * 20];

int nodes;

void update(int node, int st, int dr, int l, int r) {
    if(aint[node].sum == dr - st + 1){
        return;
    }
    if(l <= st && dr <= r) {
        aint[node].sum = dr - st + 1;
        return;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    if(l <= mid) {
        update(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        update(aint[node].r, mid + 1, dr, l, r);
    }
    aint[node].sum = aint[aint[node].l].sum + aint[aint[node].r].sum;
}

int query(int node, int st, int dr, int l, int r) {
    if(aint[node].sum == dr - st + 1) return min(dr, r) - max(l, st) + 1;
  	if(aint[node].sum == 0) return 0;
    if(l <= st && dr <= r) {
        return aint[node].sum;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    int sol = 0;
    if(l <= mid) {
        sol += query(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        sol += query(aint[node].r, mid + 1, dr, l, r);
    }
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    nodes = 1;
    aint[nodes].init();
    int q;
    cin >> q;
    int ans = 0;
    while(q--){
        int a, b, c;
        cin >> a >> b >> c;
        b += ans;
        c += ans;
        if(a == 2){
            update(1, 1, VMAX, b, c);
        }else{
            ans = query(1, 1, VMAX, b, c);
            cout << ans << "\n";
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 17 ms 468 KB Output is correct
9 Correct 36 ms 692 KB Output is correct
10 Correct 36 ms 664 KB Output is correct
11 Correct 34 ms 652 KB Output is correct
12 Correct 36 ms 720 KB Output is correct
13 Correct 41 ms 748 KB Output is correct
14 Correct 41 ms 2776 KB Output is correct
15 Correct 34 ms 2964 KB Output is correct
16 Correct 40 ms 2964 KB Output is correct
17 Correct 41 ms 2892 KB Output is correct
18 Correct 45 ms 2880 KB Output is correct
19 Correct 34 ms 2880 KB Output is correct
20 Correct 34 ms 2896 KB Output is correct