Submission #945141

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945141	2024-03-13T12:44:28 Z	infrapolar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	378 ms	262144 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 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	6488 KB	Output is correct
5	Correct	12 ms	7772 KB	Output is correct
6	Correct	12 ms	7540 KB	Output is correct
7	Correct	13 ms	7772 KB	Output is correct
8	Correct	100 ms	58196 KB	Output is correct
9	Correct	203 ms	100692 KB	Output is correct
10	Correct	218 ms	111440 KB	Output is correct
11	Correct	221 ms	119540 KB	Output is correct
12	Correct	229 ms	123484 KB	Output is correct
13	Correct	197 ms	143716 KB	Output is correct
14	Correct	200 ms	144984 KB	Output is correct
15	Runtime error	378 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-