Submission #442729

#	Time	Username	Problem	Language	Result	Execution time	Memory
442729		SirCovidThe19th	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	200 ms	3048 KiB

apple

#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 / 100