Submission #1324120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324120		sh_qaxxorov_571	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	295 ms	137272 KiB

apple

#include <iostream>
#include <algorithm>

using namespace std;

/**
 * Dinamik Segment Tree - Har bir tugun kerak bo'lganda xotiradan joy oladi.
 * Vaqt murakkabligi: O(M log 10^9)
 * Xotira murakkabligi: O(M log 10^9)
 */

struct Node {
    int sum;
    int lazy; // 1 bo'lsa, ushbu oraliq to'liq pishgan
    Node *left, *right;

    Node() : sum(0), lazy(0), left(nullptr), right(nullptr) {}

    void push(int l, int r) {
        if (lazy) {
            int mid = l + (r - l) / 2;
            if (!left) left = new Node();
            if (!right) right = new Node();
            left->sum = (mid - l + 1);
            left->lazy = 1;
            right->sum = (r - mid);
            right->lazy = 1;
            lazy = 0;
        }
    }
};

Node* root = new Node();
const int MAX_VAL = 1e9;

void update(Node* curr, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        curr->sum = (r - l + 1);
        curr->lazy = 1;
        return;
    }
    curr->push(l, r);
    int mid = l + (r - l) / 2;
    if (ql <= mid) {
        if (!curr->left) curr->left = new Node();
        update(curr->left, l, mid, ql, qr);
    }
    if (qr > mid) {
        if (!curr->right) curr->right = new Node();
        update(curr->right, mid + 1, r, ql, qr);
    }
    curr->sum = (curr->left ? curr->left->sum : 0) + (curr->right ? curr->right->sum : 0);
}

int query(Node* curr, int l, int r, int ql, int qr) {
    if (!curr) return 0;
    if (ql <= l && r <= qr) return curr->sum;
    curr->push(l, r);
    int mid = l + (r - l) / 2;
    int res = 0;
    if (ql <= mid) res += query(curr->left, l, mid, ql, qr);
    if (qr > mid) res += query(curr->right, mid + 1, r, ql, qr);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M;
    if (!(cin >> M)) return 0;

    int C = 0;
    while (M--) {
        int D, X, Y;
        cin >> D >> X >> Y;
        int ql = X + C;
        int qr = Y + C;

        if (D == 1) {
            C = query(root, 1, MAX_VAL, ql, qr);
            cout << C << "\n";
        } else {
            update(root, 1, MAX_VAL, ql, qr);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100