Submission #334397

#TimeUsernameProblemLanguageResultExecution timeMemory
334397NhoxZujiMonkey and Apple-trees (IZhO12_apple)C++14
0 / 100
565 ms262144 KiB
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define fi first
#define se second
#define fr(x, y, z) for (int x = y; x <= z; ++x)
#define loop(x) while(x--)
#define read(x)  freopen(x".INP","r",stdin);
#define write(x) freopen(x".OUT","w",stdout);
#define nametask "f"

using namespace std;
typedef long long ll;

int n, cnt = 1;
struct node{
    int s, l, r, lid, rid, lazy;
    node() : s(0), lid(-1), rid(-1), lazy(0) {}
};
int const maxn = 1e6 + 5;
node st[6 * maxn];

void newleft(int id){
    if (st[id].lid == -1){
        int nod;
        st[id].lid = nod = ++cnt;
        st[nod].l = st[id].l; st[nod].r = (st[id].r + st[id].l) >> 1;
    }
}

void newright(int id){
    if (st[id].rid == -1){
        int nod;
        st[id].rid = nod = ++cnt;
        st[nod].l = ((st[id].r + st[id].l) >> 1) + 1; st[nod].r = st[id].r;
    }
}

void plazy(int id){
    if (st[id].lazy){
        newleft(id); newright(id);
        st[id].s = st[id].r - st[id].l + 1;
        st[st[id].lid].lazy = st[st[id].rid].lazy = 1;
        st[id].lazy = 0;
    }
}

void upd(int id, int l, int r){
    plazy(id);
    if (st[id].l == l && st[id].r == r){
        st[id].lazy = 1;
        plazy(id);
    } else
    {
        newleft(id); newright(id);
        int mid = (st[id].l + st[id].r) >> 1;
        if (l > mid)  upd(st[id].rid, l, r); else
        if (r <= mid) upd(st[id].lid, l, r); else{
            upd(st[id].lid, l, mid);
            upd(st[id].rid, mid + 1, r);
        }

        plazy(st[id].lid); plazy(st[id].rid);
        st[id].s = st[st[id].lid].s + st[st[id].rid].s;
    }
}

int query(int id, int l, int r){
    plazy(id);
    if (st[id].l == l && st[id].r == r) return st[id].s; else
    {
        newleft(id); newright(id);
        int mid = (st[id].l + st[id].r) >> 1;
        if (l > mid)  return query(st[id].rid, l, r); else
        if (r <= mid) return query(st[id].lid, l, r); else
        return query(st[id].lid, l, mid) + query(st[id].rid, mid + 1, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //read(nametask); write(nametask);
    cin >> n;
    st[1].l = 1; st[1].r = (int) 1e9;

    int c = 0;
    for (int i = 1; i <= n; ++i){
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1){
            c = query(1, x + c, y + c);
            cout << c << "\n";
        } else upd(1, x + c, y + c);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...