Submission #888540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888540	2023-12-17T16:55:17 Z	dwuy	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	333 ms	137384 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 || !cur->sum) 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	3408 KB	Output is correct
5	Correct	16 ms	3932 KB	Output is correct
6	Correct	16 ms	3848 KB	Output is correct
7	Correct	17 ms	3932 KB	Output is correct
8	Correct	107 ms	29300 KB	Output is correct
9	Correct	228 ms	50656 KB	Output is correct
10	Correct	249 ms	56400 KB	Output is correct
11	Correct	231 ms	60240 KB	Output is correct
12	Correct	232 ms	62032 KB	Output is correct
13	Correct	230 ms	72460 KB	Output is correct
14	Correct	225 ms	72884 KB	Output is correct
15	Correct	325 ms	133460 KB	Output is correct
16	Correct	318 ms	134380 KB	Output is correct
17	Correct	226 ms	75480 KB	Output is correct
18	Correct	231 ms	75572 KB	Output is correct
19	Correct	324 ms	137304 KB	Output is correct
20	Correct	333 ms	137384 KB	Output is correct