| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 874216 | sleepntsheep | Untitled (POI11_rot) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}