Submission #1004727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1004727	2024-06-21T13:15:50 Z	turneja	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	382 ms	232544 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int R = 1e9 + 5;

struct Node {
    int val;
    bool lazy;
    struct Node* left;
    struct Node* right;
};

void compose(Node* parent, Node* node) {
    node->lazy |= parent->lazy;
}

void apply(Node* node, int l, int r) {
    if (node->lazy) {
        node->val = r - l + 1;
    }
    if (l != r) {
        if (node->left == nullptr) {
            node->left = new Node();
        }
        compose(node, node->left);
        if (node->right == nullptr) {
            node->right = new Node();
        }
        compose(node, node->right);
    }
    node->lazy = false;
}

void setUpdate(Node* node, int l, int r, int lq, int rq) {
    if (l > rq || lq > r) {
        return;
    }
    if (lq <= l && rq >= r) {
        node->lazy = true;
        return;
    }
    int mid = (l + r) / 2;
    apply(node, l, r);
    if (node->left == nullptr) {
        node->left = new Node();
    }
    setUpdate(node->left, l, mid, lq, rq);

    if (node->right == nullptr) {
        node->right = new Node();
    }
    setUpdate(node->right, mid + 1, r, lq, rq);

    apply(node->left, l, mid);
    apply(node->right, mid + 1, r);
    node->val = 0;
    if (node->left != nullptr) {
        node->val += node->left->val;
    }
    if (node->right != nullptr) {
        node->val += node->right->val;
    }
}

int query(Node* node, int l, int r, int lq, int rq) {
    if (r < lq || l > rq) {
        return 0;
    }
    apply(node, l, r);

    if (lq <= l && rq >= r) {
        return node->val;
    }

    int mid = (l + r) / 2, ans = 0;
    if (node->left != nullptr) {
        ans += query(node->left, l, mid, lq, rq);
    }
    if (node->right != nullptr) {
        ans += query(node->right, mid + 1, r, lq, rq);
    }
    return ans;
}

int main() {
    IOS;
    struct Node* root = new Node();
    int q;
    cin >> q;
    int c = 0;
    for (int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if (t == 2) {
            int l, r;
            cin >> l >> r;
            setUpdate(root, 0, R - 1, l + c, r + c);
        } else {
            int l, r;
            cin >> l >> r;
            int q = query(root, 0, R - 1, l + c, r + c);
            cout << q << endl;
            c = q;
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	5336 KB	Output is correct
5	Correct	18 ms	6568 KB	Output is correct
6	Correct	14 ms	6236 KB	Output is correct
7	Correct	14 ms	6376 KB	Output is correct
8	Correct	104 ms	47208 KB	Output is correct
9	Correct	204 ms	80976 KB	Output is correct
10	Correct	224 ms	90508 KB	Output is correct
11	Correct	266 ms	97872 KB	Output is correct
12	Correct	269 ms	100944 KB	Output is correct
13	Correct	239 ms	123216 KB	Output is correct
14	Correct	235 ms	124752 KB	Output is correct
15	Correct	371 ms	225876 KB	Output is correct
16	Correct	369 ms	227372 KB	Output is correct
17	Correct	239 ms	129108 KB	Output is correct
18	Correct	241 ms	129108 KB	Output is correct
19	Correct	359 ms	232532 KB	Output is correct
20	Correct	382 ms	232544 KB	Output is correct