Submission #607217

#TimeUsernameProblemLanguageResultExecution timeMemory
607217ertoMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h>
typedef long long int ll;
#define INF 1000000007
#define INF2 998244353
#define N (ll)(5e3+ 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))
 
int m, g, h, t, cur=0;
 
struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;
 
    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }
 
    void extend() {
        if (!left_child && left < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t + 1, right);
        }
        if(sum == right - left + 1 && left_child){
            left_child->sum = left_child->right - left_child->left + 1;
            right_child->sum = right_child->right - right_child->left + 1;
        }
    }
 
    void add(int lq, int rq) {
        if(left > rq || right < lq)return;
        if(left >= lq && right <= rq){
            if(sum == right - left + 1)return;
            sum = right - left + 1;
            return;
        }
        extend();
        left_child->add(lq, rq);
        right_child->add(lq, rq);
        sum = left_child->sum + right_child->sum;
    }
 
    int get_sum(int lq, int rq) {
        if(sum == 0 || left > rq || right < lq)return 0;
        if (lq <= left && right <= rq){
            return sum;
        }
        if(sum == right - left + 1){
            if(right>=lq && left <= lq)return rq - lq + 1;
            else if(right >= lq)return rq - left + 1;
            else if(left<=lq)return right - lq + 1;
        }
 
        extend();
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};
 
void solve(){
    cin >> m;
 
    Vertex s(1, 1e9);
 
    for(int i=1; i<=m; i++){
        cin >> t >> g >> h;
        if(t == 1){
            cur = s.get_sum(g + cur, h + cur);
            cout << cur << "\n";
        }
        else{
            s.add(g + cur, h + cur);
        }
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
   // cin>>T;
    while (T--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...