Submission #521166

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

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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:9:12: warning: 'Node::r' will be initialized after [-Wreorder]
    9 |     int l, r;
      |            ^
apple.cpp:8:9: warning:   'int Node::v' [-Wreorder]
    8 |     int v;
      |         ^
apple.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	18 ms	7584 KB	Output is correct
5	Correct	29 ms	9176 KB	Output is correct
6	Correct	24 ms	8896 KB	Output is correct
7	Correct	24 ms	9208 KB	Output is correct
8	Correct	176 ms	69348 KB	Output is correct
9	Correct	333 ms	118464 KB	Output is correct
10	Correct	348 ms	132612 KB	Output is correct
11	Correct	386 ms	143512 KB	Output is correct
12	Correct	365 ms	148268 KB	Output is correct
13	Correct	357 ms	181268 KB	Output is correct
14	Correct	369 ms	183452 KB	Output is correct
15	Runtime error	471 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-