답안 #854619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854619	2023-09-28T07:50:51 Z	anarch_y	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	325 ms	203080 KB

apple

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define pb push_back
#define int long long

const int maxn = 1e9;

struct node{
    int value, lzSet;
    node *left, *right;
    node(int v){
        value = v; lzSet = -1;
        left = right = nullptr;
    }
};

struct DynamicTree{
    int len;
    node *root;
    DynamicTree(int N){
        int p = ceil(log2(N));
        len = 1<<p;
        root = new node(0);
    }

    void pushup(node *k){
        int sum = 0;
        if(k->left != nullptr) sum += k->left->value;
        if(k->right != nullptr) sum += k->right->value;
        k->value = sum;
    }

    void pushdown(node *k, int x, int y){
        int v = k->lzSet;
        int d = (x+y)/2;
        if(v != -1){
            if(k->left == nullptr) k->left = new node(0);
            if(k->right == nullptr) k->right = new node(0);

            k->left->lzSet = v;
            k->right->lzSet = v;

            k->left->value = (d-x+1)*v;
            k->right->value = (y-d)*v;
            k->lzSet = -1;
        }
    }

    void update(int a, int b, int v, node *k, int x, int y){
        if(a<=x and y<=b){
            k->value = (y-x+1)*v;
            k->lzSet = v;
            return;
        }
        pushdown(k, x, y);
        int d = (x+y)/2;
        if(d>=a and x<=b){
            if(k->left == nullptr) k->left = new node(0);
            update(a, b, v, k->left, x, d);
        }
        if(y>=a and d+1<=b){
            if(k->right == nullptr) k->right = new node(0);
            update(a, b, v, k->right, d+1, y);
        }
        pushup(k);
    }

    void update(int a, int b, int v){
        update(a, b, v, root, 0, len-1);
    }

    int query(int a, int b, node *k, int x, int y){
        if(k == nullptr) return 0LL;
        if(b<x or a>y) return 0LL;
        if(a<=x and y<=b) return k->value;
        pushdown(k, x, y);
        int d = (x+y)/2;
        int s1 = query(a, b, k->left, x, d);
        int s2 = query(a, b, k->right, d+1, y);
        return s1+s2;
    }

    int query(int a, int b){
        return query(a, b, root, 0, len-1);
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M; cin >> M;
    DynamicTree dseg(maxn);
    
    int C = 0;
    while(M--){
        int op; cin >> op;
        if(op==2){
            int a, b; cin >> a >> b; a--; b--;
            dseg.update(a+C, b+C, 1);
        }
        else{
            int a, b; cin >> a >> b; a--; b--;
            int ans = dseg.query(a+C, b+C);
            C = ans;
            cout << ans << "\n";
        }
    }
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	9 ms	4900 KB	Output is correct
5	Correct	11 ms	5724 KB	Output is correct
6	Correct	11 ms	5584 KB	Output is correct
7	Correct	11 ms	5724 KB	Output is correct
8	Correct	89 ms	42840 KB	Output is correct
9	Correct	212 ms	76628 KB	Output is correct
10	Correct	208 ms	81900 KB	Output is correct
11	Correct	195 ms	88144 KB	Output is correct
12	Correct	205 ms	90712 KB	Output is correct
13	Correct	183 ms	107608 KB	Output is correct
14	Correct	186 ms	108448 KB	Output is correct
15	Correct	325 ms	196724 KB	Output is correct
16	Correct	306 ms	198216 KB	Output is correct
17	Correct	187 ms	112264 KB	Output is correct
18	Correct	190 ms	112344 KB	Output is correct
19	Correct	312 ms	202604 KB	Output is correct
20	Correct	312 ms	203080 KB	Output is correct