Submission #607179

#	Time	Username	Problem	Language	Result	Execution time	Memory
607179		erto	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	212 KiB

apple

#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 lazy=0;
    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(lazy == 1 && left_child){
            left_child->lazy = 1;
            right_child->lazy = 1;
            left_child->sum = left_child->right - left_child->left + 1;
            right_child->sum = right_child->right - right_child->left + 1;
            lazy = 0;
        }
    }

    void add(int lq, int rq) {
        if(left > rq || right < lq)return;
        if(left >= lq && right <= rq){
            if(sum == right - left + 1)return;
            lazy = 1;
            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(lq > left){
                return right - lq + 1;
            }
            else{
                return rq - left + 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();
    }
}

• Subtask 1: 0 / 100