#include <assert.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <stdint.h> #define N 1000000 #define M (20*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; }

rot.c: In function 'read':
rot.c:25:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", a+v);
      |     ^~~~~~~~~~~~~~~~
rot.c: In function 'main':
rot.c:98:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~