답안 #339792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339792 2020-12-26T08:23:41 Z Vladikus004 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
522 ms 207812 KB
#include <bits/stdc++.h>
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

struct node{
    int sum, tl, tr, mod;
    node *l, *r;
    node(){
        sum = 0; tl = tr = mod = -1;
        l = r = nullptr;
    }
    node(int L, int R, int SUM){
        sum = SUM; tl = L; tr = R;
        mod = -1;
        l = r = nullptr;
    }
};

const int SZ = (int)1e9+3;
node *root = new node(0, SZ, 0);

void push(node *v){
    if (v->tl == v->tr) return;
    int tm = (v->tl + v->tr) / 2;
    if (!v->l)
        v->l = new node(v->tl, tm, 0);
    if (!v->r)
        v->r = new node(tm + 1, v->tr, 0);
    if (v->mod != -1){
        v->l->mod = v->mod;
        v->r->mod = v->mod;
        v->l->sum = (v->l->tr - v->l->tl + 1) * (v->mod);
        v->r->sum = (v->r->tr - v->r->tl + 1) * (v->mod);
        v->mod = -1;
    }
}

void up(node *v, int l, int r, int val){
    if (l > r) return;
    if (v->tl == l && v->tr == r) {
        v->sum = val * (v->tr - v->tl + 1);
        v->mod = val;
        return;
    }
    push(v);
    int tm = (v->tr + v->tl) / 2;
    up(v->l, l, min(r, tm), val);
    up(v->r, max(tm + 1, l), r, val);
    v->sum = v->l->sum + v->r->sum;
}

int get_sum(node *v, int l, int r){
    if (l > r) return 0;
    if (v->tl == l && v->tr == r) return v->sum;
    push(v);
    int tm = (v->tr + v->tl) / 2;
    int ans = 0;
    ans += get_sum(v->l, l, min(r, tm));
    ans += get_sum(v->r, max(l, tm + 1), r);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);
    int m;
    cin >> m;
    int c = 0;
    while (m--){
        int tp,l,r;
        cin >> tp >> l >> r;
        if (tp == 1){
            cout << (c = get_sum(root, l + c, r + c))    << "\n";
//            up(root, l + c, r + c, 0);
        }else{
            up(root, l + c, r + c, 1);
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 20 ms 5100 KB Output is correct
5 Correct 20 ms 6124 KB Output is correct
6 Correct 19 ms 5868 KB Output is correct
7 Correct 21 ms 6124 KB Output is correct
8 Correct 161 ms 44652 KB Output is correct
9 Correct 321 ms 77548 KB Output is correct
10 Correct 334 ms 85484 KB Output is correct
11 Correct 340 ms 91756 KB Output is correct
12 Correct 338 ms 94572 KB Output is correct
13 Correct 314 ms 110060 KB Output is correct
14 Correct 342 ms 111212 KB Output is correct
15 Correct 519 ms 201708 KB Output is correct
16 Correct 522 ms 203444 KB Output is correct
17 Correct 338 ms 115052 KB Output is correct
18 Correct 325 ms 114884 KB Output is correct
19 Correct 513 ms 207812 KB Output is correct
20 Correct 513 ms 207724 KB Output is correct