Submission #867641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867641	2023-10-29T03:59:32 Z	sleepntsheep	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	262144 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8540 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Correct	1 ms	8664 KB	Output is correct
4	Correct	10 ms	13800 KB	Output is correct
5	Correct	12 ms	13916 KB	Output is correct
6	Correct	12 ms	13916 KB	Output is correct
7	Correct	13 ms	13916 KB	Output is correct
8	Correct	95 ms	48980 KB	Output is correct
9	Correct	191 ms	75072 KB	Output is correct
10	Correct	225 ms	84492 KB	Output is correct
11	Correct	229 ms	89680 KB	Output is correct
12	Correct	215 ms	92244 KB	Output is correct
13	Correct	175 ms	112472 KB	Output is correct
14	Correct	195 ms	114768 KB	Output is correct
15	Execution timed out	2579 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-