Submission #945149

#	Time	Username	Problem	Language	Result	Execution time	Memory
945149		infrapolar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	31 ms	3156 KiB

apple

#include <bits/stdc++.h>
using namespace std;
struct Node{
    Node *left = nullptr, *right = nullptr;
    int64_t count = 0;
    bool red = false;
    int64_t node_l, node_r;
    Node(int64_t l, int64_t r){ 
        node_l = l; 
        node_r = r;
    }
    void check_children(){
        int64_t mid = (node_l + node_r);
        if (mid < 0LL){
            mid -= 1;
        }
        mid /= 2LL;
        if (left == nullptr)
            left = new Node(node_l, mid);
        if (right == nullptr)
            right = new Node(mid+1, node_r);

    }
    void paint(int64_t l, int64_t r){
        if (l > node_r || r < node_l)
            return;
        if (l <= node_l && node_r <= r){
            red = true;
            count = node_r - node_l+1;
            return;
        }
        if (red)
            return;
        check_children();
        left->paint(l, r);
        right->paint(l, r);
        count = left->count + right->count;
    }
    int64_t get(int64_t l, int64_t r){

        if (l > node_r || r < node_l)
            return 0;
        if (l <= node_l && node_r <= r){
            return count;
        }
        if (red)
            return min(node_r, r) - max(node_l, l) + 1;
        check_children();
        return left->get(l, r) + right->get(l, r);
    }
};
void solve(){
    Node root(1, 1e9);
    int m;
    cin >> m;
    int64_t c = 0;
    for (int i = 0; i < m; i++)
    {
        int64_t t, l, r;
        cin >> t >> l >> r;
        l += c;
        r += c;
        if (t == 1){
            c = root.get(l, r);
            cout << c << '\n';
        }
        else{
            root.paint(l, r);
        }
    }
    
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    solve();
}

• Subtask 1: 100 / 100