oj.uz

답안 #1010276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010276 2024-06-28T16:12:06 Z phoenix 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 120 ms 63488 KB 
#include <bits/stdc++.h>

using namespace std;

struct node {
    int l;
    int r;
    int s;
    bool upd;
    node() : l(0), r(0), s(0), upd(0) {}
};

const int A = (1 << 30) - 1;
const int MAX_SZ = 4'000'000;

int sz = 0;
node st[MAX_SZ];


void setpush(int v, int l, int r) {
    st[v].s = r - l + 1;
    st[v].upd = true;
}

void push(int v, int l, int r) {
    int mid = (l + r) / 2;
    int L = st[v].l, R = st[v].r;
    if (!L) {
        L = st[v].l = ++sz;
        st[L] = node();
    }
    if (!R) {
        R = st[v].r = ++sz;
        st[R] = node();
    }
    if (!st[v].upd) return;
    setpush(L, l, mid);
    setpush(R, mid + 1, r);
    st[v].upd = false;
}

void update(int ql, int qr, int l = 0, int r = A, int v = 1) {
    if (r < ql || l > qr) 
        return;
    if (ql <= l && r <= qr) {
        setpush(v, l, r);
        return;
    }
    push(v, l, r);
    int mid = (l + r) / 2;
    update(ql, qr, l, mid, st[v].l);
    update(ql, qr, mid + 1, r, st[v].r);
    st[v].s = st[st[v].l].s + st[st[v].r].s;
}
int get(int ql, int qr, int l = 0, int r = A, int v = 1) {
    if (r < ql || l > qr) 
        return 0;
    if (ql <= l && r <= qr) {
        return st[v].s;
    }
    push(v, l, r);
    int mid = (l + r) / 2; 
    return get(ql, qr, l, mid, st[v].l) 
         + get(ql, qr, mid + 1, r, st[v].r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    st[++sz] = node();
    int M;
    cin >> M;
    int c = 0;
    while (M--) {
        int d, l, r;
        cin >> d >> l >> r;
        l += c, r += c;
        if (d == 1) {
            c = get(l, r);
            cout << c << '\n';
        } else {
            update(l, r);
        }
    }
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 63068 KB Output is correct
2 Correct 10 ms 62880 KB Output is correct
3 Correct 10 ms 63068 KB Output is correct
4 Correct 16 ms 62904 KB Output is correct
5 Correct 17 ms 63064 KB Output is correct
6 Correct 18 ms 63068 KB Output is correct
7 Correct 17 ms 63064 KB Output is correct
8 Correct 52 ms 63068 KB Output is correct
9 Correct 115 ms 63404 KB Output is correct
10 Correct 99 ms 63440 KB Output is correct
11 Correct 104 ms 63316 KB Output is correct
12 Correct 102 ms 63388 KB Output is correct
13 Correct 107 ms 63316 KB Output is correct
14 Correct 103 ms 63488 KB Output is correct
15 Incorrect 120 ms 63296 KB Output isn't correct
16 Halted 0 ms 0 KB -