Submission #521168

#	Time	Username	Problem	Language	Result	Execution time	Memory
521168		Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	601 ms	262144 KiB

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 (stderr)

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 / 100