제출 #867642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867642		sleepntsheep	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	270 ms	173364 KiB

apple

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 200005
#define M 80*N

int ALLOC = 1, A[M], L[M], R[M], TL[M], TR[M];

int sparse0(int tl, int tr, int x)
{
    TL[ALLOC] = tl, TR[ALLOC] = tr; A[ALLOC] = x; return ALLOC++;
}

void push(int v)
{
    if (!L[v] && TL[v] != TR[v])
    {
        int m = (TL[v] + TR[v])/2;
        L[v] = sparse0(TL[v], m, 0);
        R[v] = sparse0(m+1, TR[v], 0);
    }
    if (A[v] == TR[v] - TL[v] + 1)
    {
        if (TL[v] != TR[v])
            A[L[v]] = TR[L[v]] - TL[L[v]] + 1, A[R[v]] = TR[R[v]] - TL[R[v]] + 1;
    }
}

void ripe(int v, int x, int y)
{
    push(v);
    int l = TL[v], r = TR[v];
    if (r < x || y < l) return;
    if (x <= l && r <= y) { A[v] = r-l+1; push(v); return; }
    ripe(L[v], x, y), ripe(R[v], x, y); A[v] = A[L[v]] + A[R[v]];
}

int query(int v, int x, int y)
{
    push(v);
    int l = TL[v], r = TR[v];
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) return A[v];
    assert(l!=r);
    return query(L[v], x, y) + query(R[v], x, y);
}

int main()
{
    sparse0(1, 1e9, 0);
    ShinLena;
    int m = 1, d, x, y, c = 0;
    for (cin >> m; m--;)
    {
        cin >> d >> x >> y;
        if (d == 1) cout << (c = query(1, x+c, y+c)) << '\n';
        else ripe(1, x+c, y+c);
    }
    return 0;
}

• Subtask 1: 100 / 100