#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define N 3000000
#define M (40*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:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | scanf("%d", a+v);
| ~~~~~^~~~~~~~~~~
rot.cpp: In function 'int main()':
rot.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(assert.o): in function `__assert_fail_base':
(.text+0x114): relocation truncated to fit: R_X86_64_PC32 against symbol `__abort_msg' defined in .bss section in /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(abort.o)
/usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/libc.a(loadmsgcat.o): in function `_nl_load_domain':
(.text+0x3c): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x5a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x61): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x67): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x73): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x48a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4a1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4ac): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x4c2): relocation truncated to fit: R_X86_64_PC32 against `.bss'
(.text+0x510): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status
