Submission #945141

#	Time	Username	Problem	Language	Result	Execution time	Memory
945141		infrapolar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	378 ms	262144 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 push(){
        check_children();
        if (!red)
            return;
        Node* child = left;
        for (int i = 0; i < 2; i++)
        {
            child->red = true;
            child->count = child->node_r - child->node_l + 1;
            child = right;
        }

    }
    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;
        }
        push();
        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;
        }
        push();
        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: 0 / 100