Submission #1310300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310300		anandswaroop191	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	119 ms	2572 KiB

apple

// https://oj.uz/problem/view/IZhO12_apple
#include <bits/stdc++.h>

using namespace std;
#define double long double
#define int long long
#define V vector

const int inf = numeric_limits<int>::max();
const double infd = numeric_limits<double>::infinity();
using pii = pair<int, int>;
using pil = pair<int, double>;
using pli = pair<double, int>;
using pll = pair<double, double>;

#define F first
#define S second
#define PB push_back
#define read(arr) for (auto &x : arr) cin >> x
#define show(arr) for (auto x : arr) cout << x << " "; cout << endl
#define FOR(v,l,h) for (int v = l; v < h; v ++)

struct Node
{
    int l, r, v;
    Node *ln, *rn;
    bool active;
};

void u(Node *node, int ql, int qr)
{
    if (qr < node->l || node->r < ql) return;
    if (ql <= node->l && node->r <= qr)
    {
        node->v = node->r - node->l + 1;
        node->active = true;
        return;
    }
    if (node->active) return;
    int m = (node->l + node->r) / 2;
    if (node->ln == nullptr)
        node->ln = new Node{node->l, m, 0, nullptr, nullptr, false},
        node->rn = new Node{m + 1, node->r, 0, nullptr, nullptr, false};
    assert(node->ln != nullptr);
    assert(node->rn != nullptr);
    u(node->ln, ql, qr);
    u(node->rn, ql, qr);
    node->v = node->ln->v + node->rn->v;
}

int qu(Node *node, int ql, int qr)
{
    if (qr < node->l || node->r < ql) return 0;
    if (ql <= node->l && node->r <= qr) return node->v;
    if (node->active) return min(node->r, qr) - max(node->l, ql) + 1;
    if (node->ln == nullptr) return 0;
    return qu(node->ln, ql, qr) + qu(node->rn, ql, qr);
}

signed main()
{
    int m;
    cin >> m;

    Node *node = new Node {1, (int) 1e9, 0, nullptr, nullptr, false};

    int c = 0;
    while (m --)
    {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1)
        {
            c = qu(node, x + c, y + c);
            cout << c << endl;
        }
        else
        {
            // printf("x=%lld, y=%lld\n", x + c, y + c);
            u(node, x + c, y + c);
        }
        // showtree(0, 0);
    }
}

• Subtask 1: 100 / 100