답안 #399276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399276 2021-05-05T13:56:18 Z snasibov05 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
384 ms 137300 KB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define double long double
#define ull unsigned long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define s second
#define f first
#define pb push_back
#define oo 1000000000000000000ll

struct node{
    int sum;
    bool lazy;
    node* left;
    node* right;

    node(){
        sum = 0;
        lazy = false;
        left = nullptr;
        right = nullptr;
    }

    void update_sum(){
        sum = 0;
        if (left != nullptr) sum += left->sum;
        if (right != nullptr) sum += right->sum;
    }

    void push(int tl, int tr){
        if (!lazy) return;
        if (left == nullptr) left = new node();
        if (right == nullptr) right = new node();

        int tm = (tl + tr) / 2;
        left->sum = tm - tl + 1;
        left->lazy = true;

        right->sum = tr - tm;
        right->lazy = true;
        
        lazy = false;
    }
};

void update(node* v, int tl, int tr, int l, int r){
    if (tl == l && tr == r){
        v->sum = r - l + 1;
        v->lazy = true;
        return;
    }

    v->push(tl, tr);

    int tm = (tl + tr) / 2;
    if (l <= tm){
        if (v->left == nullptr) v->left = new node();
        update(v->left, tl, tm, l, min(r, tm));
    }
    if (r > tm){
        if (v->right == nullptr) v->right = new node();
        update(v->right, tm+1, tr, max(tm+1, l), r);
    }

    v->update_sum();
}

int getSum(node* v, int tl, int tr, int l, int r){
    if (tl == l && tr == r){
        return v->sum;
    }

    v->push(tl, tr);

    int tm = (tl + tr) / 2;
    int res = 0;

    if (l <= tm && v->left != nullptr) res += getSum(v->left, tl, tm, l, min(r, tm));
    if (r > tm && v->right != nullptr) res += getSum(v->right, tm+1, tr, max(l, tm+1), r);

    return res;
}

void solve() {
    const int nmax = 1e9;
    int c = 0;
    int m; cin >> m;

    node* t = new node();

    for (int i = 0; i < m; ++i) {
        int type, l, r; cin >> type >> l >> r;
        l += c; r += c;
        if (type == 1){
            c = getSum(t, 1, nmax, l, r);
            cout << c << "\n";
        } else update(t, 1, nmax, l, r);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tst; tst = 1;
    //cin >> tst;
    while (tst--){
        solve();
    }

    return 0;

}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 13 ms 3308 KB Output is correct
5 Correct 17 ms 4024 KB Output is correct
6 Correct 15 ms 3916 KB Output is correct
7 Correct 16 ms 3916 KB Output is correct
8 Correct 115 ms 29196 KB Output is correct
9 Correct 238 ms 50604 KB Output is correct
10 Correct 247 ms 55956 KB Output is correct
11 Correct 249 ms 60104 KB Output is correct
12 Correct 255 ms 62056 KB Output is correct
13 Correct 236 ms 72204 KB Output is correct
14 Correct 236 ms 72832 KB Output is correct
15 Correct 378 ms 133412 KB Output is correct
16 Correct 378 ms 134212 KB Output is correct
17 Correct 248 ms 75736 KB Output is correct
18 Correct 242 ms 75428 KB Output is correct
19 Correct 373 ms 137300 KB Output is correct
20 Correct 384 ms 137284 KB Output is correct