oj.uz

답안 #874417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874417 2023-11-17T00:22:16 Z sleepntsheep Growing Trees (BOI11_grow) C++17
100 / 100
 153 ms 4184 KB 
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>

#define INLINE inline __attribute__((always_inline))
#define assert_(x) if (!(x)) __builtin_trap()

#define N 100005

unsigned seed = 0xcb1898af;

INLINE unsigned rand_(void)
{
    return seed = ((seed << 3) ^ 0x23a8f91c);
}

int A[N], B[N], S[N], L[N], R[N], D[N], AT;

INLINE int treap(int x)
{
    A[++AT] = x; B[AT] = rand(); S[AT] = 1;
    return AT;
}

INLINE void pull(int v)
{
    S[v] = 1 + S[L[v]] + S[R[v]];
}

INLINE void push(int v)
{
    if (v && D[v])
    {
        A[v] += D[v];
        D[L[v]] += D[v];
        D[R[v]] += D[v];
        D[v] = 0;
    }
}

void spliti(int v, int *l, int *r, int ind)
{
    if (!v) { *l=*r=0; return; }
    push(v);

    if (S[L[v]] < ind)
    {
        spliti(R[v], R+v, r, ind - S[L[v]] - 1);
        *l = v;
    }
    else
    {
        spliti(L[v], l, L+v, ind);
        *r = v;
    }
    pull(v);
}

void merge(int *v, int l, int r)
{
    if (!l || !r) { *v = l^r; return; }

    push(l), push(r);

    if (B[l] < B[r])
    {
        merge(L+r, l, L[r]);
        *v = r;
    }
    else
    {
        merge(R+l, R[l], r);
        *v = l;
    }

    pull(*v);
}

int order(int v, int k)
{
    if (!v) return 0;

    push(v);
    if (A[v] < k) return 1 + S[L[v]] + order(R[v], k);
    return order(L[v], k);
}

int n, q, t;
char op;

void print(int v)
{
    push(v);
    if (!v) return;
    print(L[v]);
    printf("%d ", A[v]);
    print(R[v]);
}

int H(int v) { return R[v] ? H(R[v]) : A[v]; }

INLINE void fertilize(int s, int h)
{
    int j = order(t, h);
    int y1 = 0, y2 = 0, y3 = 0, y4 = 0, y5 = 0, y6 = 0, y7 = 0, y8 = 0;
    spliti(t, &y1, &y2, j);
    spliti(y2, &y3, &y4, s);
    int x = H(y3);
    int aa = S[y3] - order(y3, x);
    int bb = order(y4, x+1);
    spliti(y3, &y5, &y6, S[y3] - aa);
    spliti(y4, &y7, &y8, bb);

    ++D[y5]; ++D[y6];
    push(y5);
    push(y6);

    merge(&y4, y6, y8);
    merge(&y3, y5, y7);
    merge(&y2, y3, y4);
    merge(&t, y1, y2);
}

INLINE void query(int x, int y)
{
    printf("%d\n", order(t, y+1) - order(t, x));
}

int main(void)
{
    srand(time(NULL));
    scanf("%d%d", &n, &q);
    int a[N];
    for (int i = 0; i < n; ++i) scanf("%d", a+i);
    std::sort(a, a+n);
    for (int i = 0; i < n; ++i) merge(&t, t, treap(a[i]));

    for (int x, y, i = 0; i < q; ++i)
    {
        scanf(" %c%d%d", &op, &x, &y);
        if (op == 'F') fertilize(x, y);
        else query(x, y);
    }
    return 0;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:135:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     for (int i = 0; i < n; ++i) scanf("%d", a+i);
      |                                 ~~~~~^~~~~~~~~~~
grow.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf(" %c%d%d", &op, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 2872 KB Output is correct
2 Correct 116 ms 3936 KB Output is correct
3 Correct 69 ms 3756 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 2 ms 656 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 37 ms 1096 KB Output is correct
6 Correct 49 ms 1228 KB Output is correct
7 Correct 6 ms 1016 KB Output is correct
8 Correct 26 ms 1292 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 1116 KB Output is correct
2 Correct 47 ms 1876 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 27 ms 1664 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 1372 KB Output is correct
2 Correct 52 ms 1880 KB Output is correct
3 Correct 9 ms 1116 KB Output is correct
4 Correct 55 ms 1876 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 2364 KB Output is correct
2 Correct 123 ms 3408 KB Output is correct
3 Correct 14 ms 1624 KB Output is correct
4 Correct 52 ms 3412 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 2600 KB Output is correct
2 Correct 124 ms 3488 KB Output is correct
3 Correct 69 ms 3412 KB Output is correct
4 Correct 14 ms 1624 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 3120 KB Output is correct
2 Correct 94 ms 3700 KB Output is correct
3 Correct 73 ms 3672 KB Output is correct
4 Correct 14 ms 1624 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 3664 KB Output is correct
2 Correct 126 ms 3412 KB Output is correct
3 Correct 32 ms 3412 KB Output is correct
4 Correct 73 ms 3668 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 3080 KB Output is correct
2 Correct 104 ms 3828 KB Output is correct
3 Correct 153 ms 4184 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 3412 KB Output is correct