oj.uz

Submission #874409

# Submission time Handle Problem Language Result Execution time Memory
874409 2023-11-16T23:48:19 Z sleepntsheep Growing Trees (BOI11_grow) C
0 / 100
 1000 ms 10308 KB 
#include <stdio.h>

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

#define N 200001

unsigned seed = 0x8321798;

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

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

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

    if (A[v] <= val)
    {
        split(R[v], R+v, r, val);
        *l = v;
    }
    else
    {
        split(L[v], l, L+v, val);
        *r = v;
    }
    pull(v);
}

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

    if (S[L[v]] < ind)
    {
        split(R[v], R+v, r, ind - S[L[v]] - 1);
        *l = v;
    }
    else
    {
        split(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]) { int T = l; l = r; r = T; }

    int y1, y2;
    split(l, &y1, &y2, A[r]);
    merge(R+r, R[r], y2);
    merge(L+r, L[r], y1);
    *v = r;
    pull(*v);
}

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

    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)
{
    if (!v) return;
    print(L[v]);
    printf("%d ", A[v]);
    print(R[v]);
}

INLINE void fertilize(int s, int h)
{
    int j = order(t, h);
    int y1 = 0, y2 = 0, y3 = 0, y4 = 0;
    spliti(t, &y1, &y2, j);
    spliti(y2, &y3, &y4, s);
    ++D[y3];
    push(y3);
    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)
{
    scanf("%d%d", &n, &q);
    for (int x, i = 0; i < n; ++i) scanf("%d", &x), merge(&t, t, treap(x));

    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.c: In function 'main':
grow.c:132:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%d%d", &n, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~
grow.c:133:36: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     for (int x, i = 0; i < n; ++i) scanf("%d", &x), merge(&t, t, treap(x));
      |                                    ^~~~~~~~~~~~~~~
grow.c:137:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         scanf(" %c%d%d", &op, &x, &y);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1026 ms 10308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 3292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 3832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 4176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 4432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 9124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 4276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 5712 KB Output isn't correct
2 Halted 0 ms 0 KB -