oj.uz

Submission #486369

# Submission time Handle Problem Language Result Execution time Memory
486369 2021-11-11T12:42:54 Z pannenkoek Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 202 ms 111812 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); i++)

using ll = long long;

int m;

struct Node{
    ll begin, end;
    bool ripe;
    Node *left, *right;

    Node(ll b, ll e){
        begin = b;
        end = e;
    }

    void ins(ll a, ll b){
        if(a <= begin && b >= end){
            ripe = true;
            return;
        } if(b < begin || a > end) return;

        if(left == NULL){
            ll mid = (begin + end) / 2;
            left = new Node(begin, mid);
            right = new Node(mid + 1, end);
        }
        left->ins(a, b);
        right->ins(a, b);
    }

    ll get(ll a, ll b){
        if(a > end || b < begin) return 0;
        if(ripe) {
            return min(end, b) - max(begin, a) + 1;
        } if(left == NULL){
            return 0;
        }
        return left->get(a, b) + right->get(a, b);
    }

} root(0, 1LL << 60);


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

    cin >> m;

    ll c = 0;
    rep(i, 0, m){
        ll d, x, y;
        cin >> d >> x >> y;

        x += c;
        y += c;

        if(d == 2){
            root.ins(x, y);
        } else {
            c = root.get(x, y);
            cout << c << "\n";
        }
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 8 ms 2848 KB Output is correct
5 Correct 10 ms 3316 KB Output is correct
6 Correct 10 ms 3276 KB Output is correct
7 Correct 10 ms 3412 KB Output is correct
8 Correct 63 ms 25180 KB Output is correct
9 Correct 135 ms 48212 KB Output is correct
10 Correct 131 ms 50764 KB Output is correct
11 Correct 133 ms 54212 KB Output is correct
12 Correct 148 ms 55420 KB Output is correct
13 Correct 139 ms 59220 KB Output is correct
14 Correct 131 ms 60640 KB Output is correct
15 Correct 188 ms 109380 KB Output is correct
16 Correct 202 ms 109760 KB Output is correct
17 Correct 129 ms 62532 KB Output is correct
18 Correct 135 ms 62432 KB Output is correct
19 Correct 195 ms 111696 KB Output is correct
20 Correct 196 ms 111812 KB Output is correct