Submission #1252331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252331		hossainrasel1042	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	320 KiB

apple

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const long long RANGE_MIN = 1;
const long long RANGE_MAX = 1000000000; // 1e9

struct Node {
    long long sum;
    bool lazy; // if true, entire segment is ripened
    Node *left, *right;
    Node() : sum(0), lazy(false), left(nullptr), right(nullptr) {}
};

class DynamicSegTree {
private:
    Node* root;

    void push(Node* node, long long l, long long r) {
        if (node->lazy && l != r) {
            if (!node->left) node->left = new Node();
            if (!node->right) node->right = new Node();

            node->left->lazy = true;
            node->right->lazy = true;

            long long mid = (l + r) / 2;
            node->left->sum = mid - l + 1;
            node->right->sum = r - mid;

            node->lazy = false;
        }
    }

    void update(Node*& node, long long l, long long r, long long ul, long long ur) {
        if (!node) node = new Node();

        if (node->lazy) return; // already fully ripened, skip

        if (ul <= l && r <= ur) {
            node->lazy = true;
            node->sum = r - l + 1;
            return;
        }

        push(node, l, r);
        long long mid = (l + r) / 2;

        if (ul <= mid) {
            if (!node->left) node->left = new Node();
            update(node->left, l, mid, ul, ur);
        }
        if (ur > mid) {
            if (!node->right) node->right = new Node();
            update(node->right, mid + 1, r, ul, ur);
        }

        node->sum = 0;
        if (node->left) node->sum += node->left->sum;
        if (node->right) node->sum += node->right->sum;
    }

    long long query(Node* node, long long l, long long r, long long ql, long long qr) {
        if (!node || qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return node->sum;

        push(node, l, r);
        long long mid = (l + r) / 2;
        long long res = 0;
        if (ql <= mid && node->left) {
            res += query(node->left, l, mid, ql, qr);
        } else if (ql <= mid) {
            // If no left child, but query overlaps, then no ripened trees there
        }
        if (qr > mid && node->right) {
            res += query(node->right, mid + 1, r, ql, qr);
        } else if (qr > mid) {
            // no contribution
        }
        return res;
    }

public:
    DynamicSegTree() {
        root = nullptr;
    }

    void update(long long l, long long r) {
        if (l > r) return;
        l = max(l, RANGE_MIN);
        r = min(r, RANGE_MAX);
        update(root, RANGE_MIN, RANGE_MAX, l, r);
    }

    long long query(long long l, long long r) {
        if (l > r) return 0;
        l = max(l, RANGE_MIN);
        r = min(r, RANGE_MAX);
        return query(root, RANGE_MIN, RANGE_MAX, l, r);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ifstream fin("f.in");
    ofstream fout("f.out");

    int M;
    fin >> M;

    DynamicSegTree segTree;
    long long C = 0;

    while (M--) {
        int D;
        long long X, Y;
        fin >> D >> X >> Y;

        long long L = X + C;
        long long R = Y + C;

        if (D == 2) {
            // Ripen apples in [L, R]
            segTree.update(L, R);
        } else if (D == 1) {
            // Query how many ripened in [L, R]
            long long res = segTree.query(L, R);
            fout << res << '\n';
            C = res; // update C for next event
        }
    }

    fin.close();
    fout.close();

    return 0;
}

• Subtask 1: 0 / 100