Submission #592661

#	Time	Username	Problem	Language	Result	Execution time	Memory
592661		boykut	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	484 ms	186356 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, LEFT, RIGHT;
    Node() : sum(0), lazy(0), LEFT(-1), RIGHT(-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].LEFT == -1) {
            t[v].LEFT = cnt++;
            t[t[v].LEFT].vl = t[v].vl;
            t[t[v].LEFT].vr = mid;
        }
        if (t[v].RIGHT == -1) {
            t[v].RIGHT = cnt++;
            t[t[v].RIGHT].vl = mid + 1;
            t[t[v].RIGHT].vr = t[v].vr;
        }
        t[t[v].LEFT].lazy = t[t[v].RIGHT].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].LEFT == -1) {
            t[v].LEFT = cnt++;
            t[t[v].LEFT].vl = t[v].vl;
            t[t[v].LEFT].vr = mid;
        }
        if (t[v].RIGHT == -1) {
            t[v].RIGHT = cnt++;
            t[t[v].RIGHT].vl = mid + 1;
            t[t[v].RIGHT].vr = t[v].vr;
        }
        if (l > mid) update(t[v].RIGHT, l, r);
        else if (r <= mid) update(t[v].LEFT, l, r);
        else {
            update(t[v].LEFT, l, mid);
            update(t[v].RIGHT, mid + 1, r);
        }
        push_lazy(t[v].LEFT);
        push_lazy(t[v].RIGHT);
        t[v].sum = t[t[v].LEFT].sum + t[t[v].RIGHT].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].LEFT == -1) {
        t[v].LEFT = cnt++;
        t[t[v].LEFT].vl = t[v].vl;
        t[t[v].LEFT].vr = mid;
    }
    if (t[v].RIGHT == -1) {
        t[v].RIGHT = cnt++;
        t[t[v].RIGHT].vl = mid + 1;
        t[t[v].RIGHT].vr = t[v].vr;
    }
    if (l > mid) return query(t[v].RIGHT, l, r);
    else if (r <= mid) return query(t[v].LEFT, l, r);
    else return query(t[v].LEFT, l, mid) + query(t[v].RIGHT, 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