Submission #592657

#	Time	Username	Problem	Language	Result	Execution time	Memory
592657		boykut	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	384 ms	188592 KiB

apple

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;


struct Node {
    int sum, lazy, vl, vr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
};


const int MAXN = 123456;
Node t[64 * MAXN];
int cnt = 2;

void push_lazy(int v) {
    if (t[v].lazy) {
        t[v].sum = t[v].vr - t[v].vl + 1;
        int mid = (t[v].vl + t[v].vr) / 2;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].vl = t[v].vl;
            t[t[v].l].vr = mid;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].vl = mid + 1;
            t[t[v].r].vr = t[v].vr;
        }
        t[t[v].l].lazy = t[t[v].r].lazy = 1;
        t[v].lazy = 0;
    }
}


void update(int v, int l, int r) {
    push_lazy(v);
    if (l == t[v].vl && r == t[v].vr) {
        t[v].lazy = 1;
        push_lazy(v);
    } else {
        int mid = (t[v].vl + t[v].vr) / 2;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].vl = t[v].vl;
            t[t[v].l].vr = mid;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].vl = mid + 1;
            t[t[v].r].vr = t[v].vr;
        }
        if (l > mid) update(t[v].r, l, r);
        else if (r <= mid) update(t[v].l, l, r);
        else {
            update(t[v].l, l, mid);
            update(t[v].r, mid + 1, r);
        }
        push_lazy(t[v].l);
        push_lazy(t[v].r);
        t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    }
}


int query(int v, int l, int r) {
    push_lazy(v);
    if (l == t[v].vl && r == t[v].vr) return t[v].sum;
    int mid = (t[v].vl + t[v].vr) / 2;
    if (t[v].l == -1) {
        t[v].l = cnt++;
        t[t[v].l].vl = t[v].vl;
        t[t[v].l].vr = mid;
    }
    if (t[v].r == -1) {
        t[v].r = cnt++;
        t[t[v].r].vl = mid + 1;
        t[t[v].r].vr = t[v].vr;
    }
    if (l > mid) return query(t[v].r, l, r);
    else if (r <= mid) return query(t[v].l, l, r);
    else return query(t[v].l, l, mid) + query(t[v].r, mid + 1, r);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;
    cin >> m;


    t[1].sum = 0; t[1].lazy = 0;
    t[1].vl = 1; t[1].vr = 1e9;


    int c = 0;

    while (m--) {
        int d, x, y;
        cin >> d >> x >> y;

        if (d == 1) {
            c = query(1, x + c, y + c);
            cout << c << '\n';
        } else update(1, x + c, y + c);
    }

    return 0;

}

• Subtask 1: 100 / 100