oj.uz

Submission #442729

# Submission time Handle Problem Language Result Execution time Memory
442729 2021-07-08T18:51:46 Z SirCovidThe19th Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
 200 ms 3048 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node{
    int ans; Node *child[2];
    void create(int i){ if (!child[i]) child[i] = new Node(); }
    void upd(int x, int y, int l = 1, int r = 1e9){
        if (ans == r-l+1) return;
        if (l >= x and r <= y){ ans = r-l+1; return; }
        int mid = (l+r)/2;
        if (mid >= x) create(0), child[0]->upd(x, y, l, mid);
        if (mid+1 <= y) create(1), child[1]->upd(x, y, mid+1, r);
        ans = ((child[0]) ? child[0]->ans : 0)+((child[1]) ? child[1]->ans : 0);
    }
    int query(int x, int y, int l = 1, int r = 1e9){
        if (l >= x and r <= y) return ans;
        if (ans == r-l+1) return min(y, r)-max(x, l)+1;
        int mid = (l+r)/2, ret = 0;
        if (mid >= x) create(0), ret += child[0]->query(x, y, l, mid);
        if (mid+1 <= y) create(1), ret += child[1]->query(x, y, mid+1, r);
        return ret;
    }
}seg;

int main(){ 
    int n, c = 0; cin >> n; 
    while (n--){
        int d, l, r; cin >> d >> l >> r; l += c, r += c;
        if (d == 2) seg.upd(l, r);
        else cout<<(c = seg.query(l, r))<<endl;
    }
}

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 1 ms 204 KB Output is correct
4 Correct 16 ms 420 KB Output is correct
5 Correct 21 ms 480 KB Output is correct
6 Correct 19 ms 476 KB Output is correct
7 Correct 19 ms 496 KB Output is correct
8 Correct 92 ms 1356 KB Output is correct
9 Correct 187 ms 2356 KB Output is correct
10 Correct 186 ms 2364 KB Output is correct
11 Correct 190 ms 2500 KB Output is correct
12 Correct 186 ms 2532 KB Output is correct
13 Correct 200 ms 2788 KB Output is correct
14 Correct 200 ms 2864 KB Output is correct
15 Correct 197 ms 3012 KB Output is correct
16 Correct 196 ms 2944 KB Output is correct
17 Correct 188 ms 2752 KB Output is correct
18 Correct 192 ms 2960 KB Output is correct
19 Correct 194 ms 2984 KB Output is correct
20 Correct 194 ms 3048 KB Output is correct