Submission #992421

#	Time	Username	Problem	Language	Result	Execution time	Memory
992421		KK_1729	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	186 ms	153424 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

struct Vertex{
    int left, right;
    int sum = 0ll; int lazy = 0ll;
    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+1ll, right);
        }
    }
    int intersection(int l, int r, int ql, int qr){
        return max(0ll, min(r, qr)-max(l, ql)+1ll);
    }
    void push(){
        if (lazy){
            left_child->lazy = 1;
            left_child->sum = left_child->right-left_child->left+1ll;

            right_child->lazy = 1;
            right_child->sum = right_child->right-right_child->left+1ll;
        }
    }
    void add(int l, int r){
        extend();
        if (lazy) return;
        if (left >= l && right <= r){
            lazy = 1;
            sum = right-left+1;
            return;
        }
        if (right < l || left > r) return;
        push();
        if (left_child){
            left_child->add(l, r);
            right_child->add(l, r);
            sum = left_child->sum+right_child->sum;
        }
    }

    int get_sum(int ql, int qr){
        if (ql <= left && right <= qr) return sum;
        if (right < ql || left > qr) return 0;
        extend();
        push();
        return left_child->get_sum(ql, qr)+right_child->get_sum(ql, qr);
    }
};

void solve(){
    Vertex root(0ll, 100000000000000ll);
    int c = 0ll;
    // root.add(1, 8);
    // root.add(2, 6);
    // cout << root.get_sum(6, 8) << endl;
    int m; cin >> m;
    while (m--){
        int d, x, y; cin >> d >> x >> y;
        if (d == 1ll){
            int e = root.get_sum(x+c, y+c);
            c = e;
            cout << e << endl;
        }else{
            root.add(x+c, y+c);
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}

• Subtask 1: 100 / 100