Submission #945135

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
945135	2024-03-13T12:41:45 Z	infrapolar	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	399 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);
    }
};
struct Edge{
    int64_t y1, y2;
    int64_t x;
    bool open;
    bool operator<(const Edge& other) const{
        if (x == other.x)
            return open > other.open;
        return x < other.x;
    }
};
void solve(){
    Node root(1, 1e9);
    int m;
    cin >> m;
    int c = 0;
    for (int i = 0; i < m; i++)
    {
        int 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	6648 KB	Output is correct
5	Correct	12 ms	8028 KB	Output is correct
6	Correct	12 ms	7772 KB	Output is correct
7	Correct	12 ms	7772 KB	Output is correct
8	Correct	107 ms	58960 KB	Output is correct
9	Correct	212 ms	102224 KB	Output is correct
10	Correct	212 ms	112980 KB	Output is correct
11	Correct	229 ms	121612 KB	Output is correct
12	Correct	233 ms	125232 KB	Output is correct
13	Correct	199 ms	145636 KB	Output is correct
14	Correct	210 ms	147080 KB	Output is correct
15	Runtime error	399 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-