Submission #1213519

#TimeUsernameProblemLanguageResultExecution timeMemory
1213519domi원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
434 ms327680 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

using namespace std;

const int VMAX = 1e9;

struct Node {
    int val;
    int lazy;
    bool has_lazy;
    Node *l, *r;

    Node() : val(0), lazy(0), has_lazy(false), l(nullptr), r(nullptr) {}

    Node(Node *l, Node *r) : val(0), lazy(0), has_lazy(false), l(l), r(r) {
        if (l) val += l->val;
        if (r) val += r->val;
    }
};

Node* root = nullptr;
int n, C;

void push(Node*& nod, int st, int dr) {
    if (!nod) nod = new Node();
    if (nod->has_lazy) {
        nod->val = (dr - st + 1) * nod->lazy;
        if (st != dr) {
            if (!nod->l) nod->l = new Node();
            if (!nod->r) nod->r = new Node();
            nod->l->lazy = nod->lazy;
            nod->r->lazy = nod->lazy;
            nod->l->has_lazy = nod->r->has_lazy = true;
        }
        nod->has_lazy = false;
    }
}

void update(Node*& nod, int l, int r, int val, int st = 1, int dr = VMAX) {
    push(nod, st, dr);
    if (st > r || dr < l) return;
    if (l <= st && dr <= r) {
        nod->lazy = val;
        nod->has_lazy = true;
        push(nod, st, dr);
        return;
    }
    int m = (st + dr) >> 1;
    update(nod->l, l, r, val, st, m);
    update(nod->r, l, r, val, m + 1, dr);
    nod->val = (nod->l ? nod->l->val : 0) + (nod->r ? nod->r->val : 0);
}

int query(Node*& nod, int l, int r, int st = 1, int dr = VMAX) {
    if (!nod || st > r || dr < l) return 0;
    push(nod, st, dr);
    if (l <= st && dr <= r) return nod->val;
    int m = (st + dr) >> 1;
    return query(nod->l, l, r, st, m) + query(nod->r, l, r, m + 1, dr);
}


signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1, d, x, y; i <= n; ++i) {
        cin >> d >> x >> y;
        if (d == 1)
            cout << (C = query(root, x + C, y + C)) << '\n';
        if (d == 2)
            update(root, x + C, y + C, 1);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...