Submission #521168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521168	2022-02-01T06:29:01 Z	Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	601 ms	262144 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define DEBUG 0
using namespace std;

class Node {
public :
    int v;
    bool lazy;
    Node *L, *R;
    Node() : v(0), lazy(false), L(NULL), R(NULL) {}
};

void check(Node *&node) {
    if(node->L == NULL) {
        node->L = new Node();
    }
    if(node->R == NULL) {
        node->R = new Node();
    }
}

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

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


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

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

int query(Node *&node, const int &l, const int &r, const int &ql, const int &qr) {
    push(node, l, r);
    if(r < ql or qr < l) {
        return 0;
    }
    if(ql <= l and r <= qr) {
        return node->v;
    }

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

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

Compilation message

apple.cpp: In function 'void push(Node*&, const int&, const int&)':
apple.cpp:30:13: warning: unused variable 'mid' [-Wunused-variable]
   30 |         int mid = (l + r) / 2;
      |             ^~~

Subtask #1

100.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	1 ms	204 KB	Output is correct
4	Correct	15 ms	5752 KB	Output is correct
5	Correct	19 ms	6928 KB	Output is correct
6	Correct	19 ms	6684 KB	Output is correct
7	Correct	20 ms	6932 KB	Output is correct
8	Correct	150 ms	51436 KB	Output is correct
9	Correct	312 ms	87428 KB	Output is correct
10	Correct	311 ms	98124 KB	Output is correct
11	Correct	394 ms	106460 KB	Output is correct
12	Correct	337 ms	110160 KB	Output is correct
13	Correct	313 ms	136904 KB	Output is correct
14	Correct	364 ms	138192 KB	Output is correct
15	Correct	556 ms	254524 KB	Output is correct
16	Correct	553 ms	256504 KB	Output is correct
17	Correct	362 ms	145396 KB	Output is correct
18	Correct	329 ms	145364 KB	Output is correct
19	Correct	573 ms	262144 KB	Output is correct
20	Correct	601 ms	262144 KB	Output is correct