제출 #1194483

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

apple

#include<bits/stdc++.h>

using namespace std;
// typedef long long ll
const int64_t sz = 1e9 + 100;
struct Seg {
    struct Node {
        int64_t a, full, i;
        int64_t l, r;
        Node() {
            a = 0;
            full = 0;
            l = -1;
            r = -1;
            i = 0;
        }
        Node(int64_t i) {
            this->i = i;
            a = 0;
            full = 0;
            l = -1;
            r = -1;
        }
    };
    vector<Node> vv;
    Seg() {
        vv.push_back(Node());
    }
    int64_t query(int64_t l, int64_t r, int64_t x, int64_t tl, int64_t tr) {
        if (r < l || tr < l || r < tl || x == -1) {
            return 0;
        }
        // cout << l << ' ' << r << ' ' << tl << ' ' << tr <<'\n';
        if (vv[x].full){
            return r-l+1;
        }
        if (l == tl && r == tr) {
            return vv[x].a;
        }
        int64_t m = (tl + tr) / 2;
        return query(l, min(r, m), vv[x].l, tl, m) + query(max(l, m + 1), r, vv[x].r, m+1, tr);
    }
    int64_t query(int64_t l, int64_t r) {
        return query(l, r, 0, 0, sz);
    }
    int64_t upd(int64_t l, int64_t r, int64_t x, int64_t tl, int64_t tr) {
        x = get(x);
        if (r < l || tr < l || r < tl || vv[x].full) {
            return x;
        }
        if (l == tl && r == tr) {
            vv[x].a = r-l+1;
            vv[x].full = 1;
            // cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << r-l+1 <<' '<< x << '\n';
            return x;
        }
        int64_t m = (tl + tr) / 2;
        int64_t ll = upd(l, min(r, m), vv[x].l, tl, m);
        int64_t rr = upd(max(l, m + 1), r, vv[x].r, m + 1, tr);
        // cout<<vv[ll].a + vv[rr].a<
        vv[x].a = vv[ll].a + vv[rr].a;
        vv[x].l = ll;
        vv[x].r = rr;
        if(tr-tl+1 == vv[x].a){
            vv[x].full = 1;
        }
        // cout << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << vv[x].a << ' '<< x <<'\n';
        return x;
    }
    void upd(int64_t l, int64_t r) {
        upd(l, r, 0, 0, sz);
    }
    int64_t get(int64_t i) {
        if (i == -1) {
            vv.push_back(Node(vv.size()));
            return vv.size()-1;
        }
        return i;
    }
};
int main() {
    int64_t a;
    cin >> a;
    int64_t all = 0;
    Seg seg;
    while (a--) {
        int64_t b, c, d;
        cin >> b >> c >> d;
        c += all;
        d += all;
        if (b == 1) {
            int64_t ret = seg.query(c, d);
            cout << ret << '\n';
            all = ret;
        } else {
            seg.upd(c, d);
        }
    }
}

• Subtask 1: 100 / 100