Submission #521165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521165	2022-02-01T06:17:37 Z	Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	426 ms	262148 KB

apple

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

class Node {
public :
    int v;
    int l, r;
    bool lazy;
    Node *L, *R;
    Node(const int &_l, const int &_r) : l(_l), r(_r), v(0), lazy(false), L(NULL), R(NULL) {}
};

void check(Node *&node, const int &l, const int &r) {
    if(node != NULL) {
        return;
    }
    node = new Node(l, r);
}

void push_lazy(Node *&node) {
    if(node->lazy == false or node->v == node->r - node->l + 1) {
        return;
    }

    node->v = node->r - node->l + 1;
    if(node->l != node->r) {
        int mid = (node->l + node->r) / 2;
        check(node->L, node->l, mid);
        check(node->R, mid + 1, node->r);
        node->L->lazy = true;
        node->R->lazy = true;
    }
    node->lazy = false;
}


void update(Node *&node, const int &ql, const int &qr) {
    push_lazy(node);
    if(ql == node->l and node->r == qr) {
        node->lazy = true;
        push_lazy(node);
        return;
    }

    int mid = (node->l + node->r) / 2;
    check(node->L, node->l, mid);
    check(node->R, mid + 1, node->r);
    if(qr <= mid) {
        update(node->L, ql, qr);
    }
    else if(mid < ql) {
        update(node->R, ql, qr);
    }
    else {
        update(node->L, ql, mid);
        update(node->R, mid + 1, qr);
    }

    push_lazy(node->L);
    push_lazy(node->R);
    node->v = node->L->v + node->R->v;
}

int query(Node *&node, const int &ql, const int &qr) {
    if(node == NULL) {
        return 0;
    }

    push_lazy(node);
    if(ql == node->l and node->r == qr) {
        return node->v;
    }

    int mid = (node->l + node->r) / 2;
    if(qr <= mid) {
        return query(node->L, ql, qr);
    }
    else if(mid < ql) {
        return query(node->R, ql, qr);
    }
    return query(node->L, ql, mid) + query(node->R, mid + 1, qr);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int m;
    cin >> m;
    int C = 0;
    Node *root = new Node(1, 1e9);
    while(m--) {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 1) {
            C = query(root, x + C, y + C);
            cout << C << '\n';
        }
        else {
            update(root, x + C, y + C);
        }
    }
    return 0;
}

Compilation message

apple.cpp: In constructor 'Node::Node(const int&, const int&)':
apple.cpp:8:12: warning: 'Node::r' will be initialized after [-Wreorder]
    8 |     int l, r;
      |            ^
apple.cpp:7:9: warning:   'int Node::v' [-Wreorder]
    7 |     int v;
      |         ^
apple.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     Node(const int &_l, const int &_r) : l(_l), r(_r), v(0), lazy(false), L(NULL), R(NULL) {}
      |     ^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	18 ms	7632 KB	Output is correct
5	Correct	25 ms	9324 KB	Output is correct
6	Correct	24 ms	9008 KB	Output is correct
7	Correct	23 ms	9232 KB	Output is correct
8	Correct	174 ms	69356 KB	Output is correct
9	Correct	340 ms	118396 KB	Output is correct
10	Correct	365 ms	132552 KB	Output is correct
11	Correct	361 ms	143452 KB	Output is correct
12	Correct	410 ms	148300 KB	Output is correct
13	Correct	348 ms	181200 KB	Output is correct
14	Correct	390 ms	183576 KB	Output is correct
15	Runtime error	426 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-