Submission #1252317

#TimeUsernameProblemLanguageResultExecution timeMemory
1252317hossainrasel1042원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

// Global EMPTY node for all unused branches
struct Node;
extern Node* const EMPTY;

struct Node {
    int val = 0, lazy = 0;
    Node *l = EMPTY, *r = EMPTY;

    Node() {} // EMPTY node constructor
    Node(int v) : val(v), lazy(0), l(EMPTY), r(EMPTY) {}
};

Node* const EMPTY = new Node(); // Singleton EMPTY node

// Push the lazy value down to children
void push(Node*& root, int l, int r) {
    if (root->lazy == 0) return;

    root->val = (r - l + 1) * root->lazy;

    if (l != r) {
        if (root->l == EMPTY) root->l = new Node();
        if (root->r == EMPTY) root->r = new Node();
        root->l->lazy = root->lazy;
        root->r->lazy = root->lazy;
    }

    root->lazy = 0;
}

// Range update: set all values in [ql, qr] to 1
void update(Node*& root, int ql, int qr, int l = 1, int r = 1e9) {
    if (qr < l || ql > r) return;
    if (root == EMPTY) root = new Node();
    push(root, l, r);
    if (ql <= l && r <= qr) {
        root->lazy = 1;
        push(root, l, r);
        return;
    }
    int m = (l + r) / 2;
    update(root->l, ql, qr, l, m);
    update(root->r, ql, qr, m + 1, r);
    root->val = root->l->val + root->r->val;
}

// Range sum query: sum of values in [ql, qr]
int query(Node*& root, int ql, int qr, int l = 1, int r = 1e9) {
    if (qr < l || ql > r || root == EMPTY) return 0;
    push(root, l, r);
    if (ql <= l && r <= qr) return root->val;
    int m = (l + r) / 2;
    return query(root->l, ql, qr, l, m) + query(root->r, ql, qr, m + 1, r);
}

void solve(int tc) {
    int q, c = 0;
    cin >> q;
    Node* root = EMPTY;

    while (q--) {
        int i, l, r;
        cin >> i >> l >> r;
        l += c, r += c;

        if (i == 1) {
            c = query(root, l, r);
            cout << c << '\n';
        } else {
            update(root, l, r);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...