Submission #521166

#	Time	Username	Problem	Language	Result	Execution time	Memory
521166		Jomnoi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	471 ms	262148 KiB

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

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