oj.uz

Submission #879526

# Submission time Handle Problem Language Result Execution time Memory
879526 2023-11-27T15:25:03 Z sleepntsheep Tree Rotations (POI11_rot) C++17
100 / 100
 156 ms 29520 KB 
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
#define N 1000000
#define M (2*N)
#define INLINE inline __attribute__((always_inline))
 
unsigned seed = 0x86868686;
 
INLINE unsigned rand_(void)
{
    return (seed << 3) ^ 0x3119475;
}
 
int n, id, a[N+1], b[N+1], c[N+1];
 
int A[M], B[M], L[M], R[M], S[M], alloc;
 
int read(void)
{
    int v = ++id;
    scanf("%d", a+v);
    if (!a[v]) b[v] = read(), c[v] = read();
    return v;
}
 
INLINE int treap0(int k)
{
    A[++alloc] = k; B[alloc] = rand_(); S[alloc] = 1;
    return alloc;
}
 
INLINE void pull(int v)
{
    S[v] = 1 + S[L[v]] + S[R[v]];
}
 
void split(int v, int *l, int *r, int val)
{
    if (!v) { *l=*r=0; return; }
 
    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);
}
 
long long inv, ans;
 
void merge(int *v, int l, int r)
{
    if (!l || !r) { *v = l^r; return; }
    int y1, y2;
    if (B[l] < B[r])
    {
        split(l, &y1, &y2, A[r]);
        inv += 1ll * S[y2] * (1+S[L[r]]);
        merge(R+r, R[r], y2);
        merge(L+r, L[r], y1);
        *v = r;
    }
    else
    {
        split(r, &y1, &y2, A[l]);
        inv += 1ll * S[y1] * (1+S[R[l]]);
        merge(R+l, R[l], y2);
        merge(L+l, L[l], y1);
        *v = l;
    }
    pull(*v);
}
 
int dfs(int u)
{
    if (a[u]) return treap0(a[u]);
    int lt = dfs(b[u]);
    int rt = dfs(c[u]);
    int v; long long c2 = 1ll*S[lt]*S[rt];
    inv = 0;
    merge(&v, lt, rt);
    ans += (inv > c2 - inv) ? c2 - inv : inv;
    return v;
}
 
 
int main()
{
    scanf("%d", &n);
    int root = read();
    dfs(root);
    printf("%lld", ans);
 
    return 0;
}

Compilation message

rot.cpp: In function 'int read()':
rot.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d", a+v);
      |     ~~~~~^~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11096 KB Output is correct
2 Correct 6 ms 10932 KB Output is correct
3 Correct 14 ms 11100 KB Output is correct
4 Correct 5 ms 11100 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11096 KB Output is correct
2 Correct 17 ms 12380 KB Output is correct
3 Correct 28 ms 13080 KB Output is correct
4 Correct 19 ms 13112 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 17236 KB Output is correct
2 Correct 31 ms 16208 KB Output is correct
3 Correct 42 ms 15188 KB Output is correct
4 Correct 156 ms 14744 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 14196 KB Output is correct
2 Correct 65 ms 15904 KB Output is correct
3 Correct 44 ms 17752 KB Output is correct
4 Correct 45 ms 17764 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 22612 KB Output is correct
2 Correct 51 ms 23128 KB Output is correct
3 Correct 99 ms 23468 KB Output is correct
4 Correct 144 ms 23120 KB Output is correct
5 Correct 89 ms 22096 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 23860 KB Output is correct
2 Correct 79 ms 28756 KB Output is correct
3 Correct 110 ms 27560 KB Output is correct
4 Correct 73 ms 29392 KB Output is correct
5 Correct 104 ms 24660 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 23844 KB Output is correct
2 Correct 119 ms 26040 KB Output is correct
3 Correct 114 ms 24952 KB Output is correct
4 Correct 102 ms 25428 KB Output is correct
5 Correct 117 ms 29520 KB Output is correct
6 Correct 74 ms 24916 KB Output is correct