제출 #1213524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213524		domi	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	286 ms	221468 KiB

apple

#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;
const int MAX_NODES = 9e6;

#pragma pack(push, 1)
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;
    }
};
#pragma pack(pop)

Node nodePool[MAX_NODES];
Node* root = nullptr;
int n, C, nodeptr;

Node* newNode() {
    assert(nodeptr < MAX_NODES);
    return &nodePool[nodeptr++];
}

void push(Node*& nod, int st, int dr) {
    if (!nod) nod = newNode();
    if (nod->has_lazy) {
        nod->val = (dr - st + 1) * nod->lazy;
        if (st != dr) {
            if (!nod->l) nod->l = newNode();
            if (!nod->r) nod->r = newNode();
            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;
}

• Subtask 1: 100 / 100