제출 #1340721

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

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second

template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;

typedef long long ll;
typedef double db;

const int mod = 1e9 + 7;

vv<int> st = {0}, val = {0};
vv<pp<int, int>> c = {{0, 0}};

void push(int node) {
    auto [u, v] = c[node];
    if (val[node]) {
        val[u] = val[v] = 1;
        st[u] = st[v] = st[node] / 2;
    }
}

void upd(int x, int y, int l, int r, int node) {
    if (val[node]) return;
    if (x <= l && y >= r) {
        st[node] = r - l + 1;
        val[node] = 1;
        return;
    }
    if (y < l || x > r) return;
    int m = (l + r) / 2;
    if (!c[node].fst) {
        c[node].fst = st.size();
        st.pb(0);
        val.pb(0);
        c.pb({0, 0});
        c[node].snd = st.size();
        st.pb(0);
        val.pb(0);
        c.pb({0, 0});
    }
    push(node);
    upd(x, y, l, m, c[node].fst);
    upd(x, y, m + 1, r, c[node].snd);
    st[node] = st[c[node].fst] + st[c[node].snd];
}

int sum(int x, int y, int l, int r, int node) {
    if (x <= l && y >= r) return st[node];
    if (y < l || x > r) return 0;
    int m = (l + r) / 2;
    if (!c[node].fst) {
        c[node].fst = st.size();
        st.pb(0);
        val.pb(0);
        c.pb({0, 0});
        c[node].snd = st.size();
        st.pb(0);
        val.pb(0);
        c.pb({0, 0});
    }
    push(node);
    return sum(x, y, l, m, c[node].fst) + sum(x, y, m + 1, r, c[node].snd);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int s = INT_MAX, c = -1, m;
    cin >> m;
    while (m--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            c = sum(l + c, r + c, 0, s, 0);
            cout << c-- << "\n";
        }
        else upd(l + c, r + c, 0, s, 0);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...