Submission #521164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521164	2022-02-01T06:15:04 Z	Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	539 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) {
        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, int ql, 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	1 ms	308 KB	Output is correct
2	Correct	1 ms	312 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	19 ms	7688 KB	Output is correct
5	Correct	23 ms	9396 KB	Output is correct
6	Correct	24 ms	9076 KB	Output is correct
7	Correct	24 ms	9344 KB	Output is correct
8	Correct	193 ms	70156 KB	Output is correct
9	Correct	358 ms	120204 KB	Output is correct
10	Correct	403 ms	134396 KB	Output is correct
11	Correct	435 ms	145224 KB	Output is correct
12	Correct	427 ms	150152 KB	Output is correct
13	Correct	415 ms	183180 KB	Output is correct
14	Correct	392 ms	185428 KB	Output is correct
15	Runtime error	539 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-