제출 #1246038

#제출 시각아이디문제언어결과실행 시간메모리
1246038inkvizytor원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
251 ms132384 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

struct vert {
    int s = 0, l = -1, p = -1;
    bool f = 0;
};

void push(int v, vector<vert> &tr) {
    if (tr[v].l != -1) {
        if (tr[v].f) {
            tr[tr[v].l].s = tr[v].s/2;
            tr[tr[v].p].s = tr[v].s/2;
            tr[tr[v].l].f = 1;
            tr[tr[v].p].f = 1;
        }
        return;
    }
    tr[v].l = tr.size();
    tr.push_back(vert());
    tr[v].p = tr.size();
    tr.push_back(vert());
    if (tr[v].f) {
        tr[tr[v].l].s = tr[v].s/2;
        tr[tr[v].p].s = tr[v].s/2;
        tr[tr[v].l].f = 1;
        tr[tr[v].p].f = 1;
    }
}

void add (int v, int p, int k, vector<vert> &tr, int a, int b) {
    if (a <= p && k <= b) {
        tr[v].s = k-p+1;
        tr[v].f = 1;
        return;
    }
    if (b < p || a > k) {
        return;
    }
    push(v, tr);
    add(tr[v].l, p, (p+k)/2, tr, a, b);
    add(tr[v].p, (p+k)/2+1, k, tr, a, b);
    tr[v].s= tr[tr[v].l].s+tr[tr[v].p].s;
}

int sum(int v, int p, int k, vector<vert> &tr, int a, int b) {
    if (a <= p && k <= b) {
        return tr[v].s;
    }
    if (b < p || a > k) {
        return 0;
    }
    push(v, tr);
    return sum(tr[v].l, p, (p+k)/2, tr, a, b)+sum(tr[v].p, (p+k)/2+1, k, tr, a, b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vert> tr (2);
    int c = 0;
    for (int i = 0; i < n; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        x+=c, y+=c;
        if (d==1) {
            int a = sum(1, 0, (1<<30)-1, tr, x, y);
            c = a;
            cout << a << '\n';
        }
        else {
            add(1, 0, (1<<30)-1, tr, x, y);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...