oj.uz

답안 #867641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867641 2023-10-29T03:59:32 Z sleepntsheep 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 2000 ms 262144 KB 
#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

# 결과 실행 시간 메모리 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 -