Submission #945149

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945149	2024-03-13T12:49:24 Z	infrapolar	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	31 ms	3156 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	3 ms	348 KB	Output is correct
6	Correct	4 ms	348 KB	Output is correct
7	Correct	3 ms	480 KB	Output is correct
8	Correct	14 ms	604 KB	Output is correct
9	Correct	28 ms	860 KB	Output is correct
10	Correct	28 ms	852 KB	Output is correct
11	Correct	27 ms	856 KB	Output is correct
12	Correct	27 ms	848 KB	Output is correct
13	Correct	30 ms	856 KB	Output is correct
14	Correct	29 ms	848 KB	Output is correct
15	Correct	27 ms	3020 KB	Output is correct
16	Correct	29 ms	3156 KB	Output is correct
17	Correct	31 ms	3016 KB	Output is correct
18	Correct	23 ms	2908 KB	Output is correct
19	Correct	26 ms	3156 KB	Output is correct
20	Correct	31 ms	3156 KB	Output is correct