Submission #888539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888539	2023-12-17T16:54:02 Z	dwuy	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	343 ms	139700 KB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node{
    bool lz;
    int sum;
    Node *l, *r;

    Node(){
        this->lz = 0;
        this->sum = 0;
        this->l = this->r = NULL;
    }
};

struct SMT{
    int n;
    Node *root;

    SMT(int n=0){
        this->n = n;
        this->root = new Node();
    }

    void down(Node *cur, int l, int r){
        if(cur->lz == 0) return;
        int mid = (l+r)>>1;
        cur->l->lz = cur->r->lz = 1;
        cur->l->sum = mid-l+1;
        cur->r->sum = r-mid;
        cur->lz = 0;
    }

    void update(Node *cur, int l, int r, const int &u, const int &v){
        if(l>v || r<u) return;
        if(l>=u && r<=v){
            cur->lz = 1;
            cur->sum = (r-l+1);
            return;
        }
        if(!cur->l) cur->l = new Node();
        if(!cur->r) cur->r = new Node();
        down(cur, l, r);
        int mid = (l+r)>>1;
        update(cur->l, l, mid, u, v);
        update(cur->r, mid+1, r, u, v);
        cur->sum = cur->l->sum + cur->r->sum;
    }

    void update(int l, int r){
        update(root, 1, n, l, r);
    }

    int get(Node *cur, int l, int r, const int &u, const int &v){
        if(l>v || r<u) return 0;
        if(l>=u && r<=v) return cur->sum;
        if(!cur->l) cur->l = new Node();
        if(!cur->r) cur->r = new Node();
        down(cur, l, r);
        int mid = (l+r)>>1;
        return get(cur->l, l, mid, u, v) + get(cur->r, mid+1, r, u, v);
    }

    int get(int l, int r){
        return get(root, 1, n, l, r);
    }
};

void solve(){
    int q;
    cin >> q;
    SMT smt(1000000000);
    int C = 0;
    while(q--){
        int oper, l, r;
        cin >> oper >> l >> r;
        l += C; r += C;
        if(oper == 2) smt.update(l, r);
        else{
            C = smt.get(l, r);
            cout << C << endl;
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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	13 ms	3520 KB	Output is correct
5	Correct	16 ms	4188 KB	Output is correct
6	Correct	16 ms	4188 KB	Output is correct
7	Correct	16 ms	4184 KB	Output is correct
8	Correct	103 ms	30188 KB	Output is correct
9	Correct	221 ms	52568 KB	Output is correct
10	Correct	221 ms	57680 KB	Output is correct
11	Correct	227 ms	61824 KB	Output is correct
12	Correct	231 ms	64112 KB	Output is correct
13	Correct	221 ms	74320 KB	Output is correct
14	Correct	225 ms	75144 KB	Output is correct
15	Correct	322 ms	135504 KB	Output is correct
16	Correct	330 ms	136776 KB	Output is correct
17	Correct	222 ms	77648 KB	Output is correct
18	Correct	228 ms	77424 KB	Output is correct
19	Correct	343 ms	139700 KB	Output is correct
20	Correct	330 ms	139600 KB	Output is correct