oj.uz

답안 #1042916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042916 2024-08-03T14:39:46 Z BF001 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 212 ms 134516 KB 
#include<bits/stdc++.h>
using namespace std;
 


struct node{
    int lc, rc, sum, lz;
    node(){
        lc = rc = -1;
        sum = lz = 0;
    }
};

vector<node> bit;
 
void acc(int id){
    if (bit[id].lc == -1){
        bit[id].lc = (int) bit.size();
        bit.push_back(node());
    }
    if (bit[id].rc == -1){
        bit[id].rc = (int) bit.size();
        bit.push_back(node());
    }
}

void add(int id, int l, int r, int val){
    bit[id].sum = val * (r - l + 1);
    bit[id].lz = val;
}

void down(int id, int l, int r){
    if (l == r || bit[id].lz == 0) return;
    acc(id);
    int mid = (l + r) >> 1;
    add(bit[id].lc, l, mid, bit[id].lz);
    add(bit[id].rc, mid + 1, r, bit[id].lz);
    bit[id].lz = 0;
}

void ud(int id, int l, int r, int u, int v, int val){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        add(id, l, r, val);
        return;
    }
    int mid = (l + r) >> 1;
    acc(id);
    down(id, l, r);
    ud(bit[id].lc, l, mid, u, v, val);
    ud(bit[id].rc, mid + 1, r, u, v, val);
    bit[id].sum = bit[bit[id].lc].sum + bit[bit[id].rc].sum;
}

int get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return bit[id].sum;
    int mid = (l + r) >> 1;
    down(id, l, r);
    int t = 0, tt = 0;
    if (bit[id].lc != -1) t = get(bit[id].lc, l, mid, u, v);
    if (bit[id].rc != -1) tt = get(bit[id].rc, mid + 1, r, u, v);
    return (t + tt);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    bit.push_back(node());

    int c = 0;
    int q;
    int n = 1e9;
    cin >> q;

    while (q--){
        int typ, l, r;
        cin >> typ >>  l >> r;
        l += c; r += c;
        if (typ == 1){
            int t = get(0, 1, n, l, r);
            c = t;
            cout << t << "\n";
            continue;
        }
        ud(0, 1, n, l, r, 1);
    }    
 
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 2608 KB Output is correct
5 Correct 8 ms 2776 KB Output is correct
6 Correct 8 ms 2768 KB Output is correct
7 Correct 8 ms 2816 KB Output is correct
8 Correct 55 ms 17596 KB Output is correct
9 Correct 109 ms 34464 KB Output is correct
10 Correct 113 ms 34460 KB Output is correct
11 Correct 119 ms 34408 KB Output is correct
12 Correct 128 ms 34460 KB Output is correct
13 Correct 126 ms 68688 KB Output is correct
14 Correct 128 ms 68476 KB Output is correct
15 Correct 207 ms 134416 KB Output is correct
16 Correct 200 ms 134452 KB Output is correct
17 Correct 128 ms 68476 KB Output is correct
18 Correct 130 ms 68472 KB Output is correct
19 Correct 212 ms 134516 KB Output is correct
20 Correct 205 ms 134456 KB Output is correct