Submission #867641

#	Time	Username	Problem	Language	Result	Execution time	Memory
867641		sleepntsheep	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2579 ms	262144 KiB

apple

#include <iostream>
#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 40*N

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

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

int sparse1(int l, int r, int tl, int tr)
{
    int p = ALLOC++;
    A[p] = A[l] + A[r];
    L[p] = l, R[p] = r; TL[p] = tl, TR[p] = tr;
    return p;
}

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 (D[v])
    {
        A[v] = (TR[v] - TL[v] + 1);
        if (TL[v] != TR[v])
            D[L[v]] = D[R[v]] = D[v];
        D[v] = 0;
    }
}

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) { D[v] = 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];
    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: 0 / 100