crossing.c

#include <stdio.h>

#define N  (1 << 19)

typedef long long int int64;

int64 seg[N << 1] = { 0 };

static inline int64 sum(int a, int b, int x, int l, int r)
{
	int v, m;
	if (a >= r || l >= b) return (0);
	if (a <= l && r <= b) return (seg[x]);
	v = x + x + 1;
	m = l + r >> 1;
	return (sum(a, b, v, l, m) + sum(a, b, v + 1, m, r));
}

int main(void)
{
	int64 ans = 0;
	int v, b;

	while (~scanf("%d", &v)){
		ans += sum(v, N, 0, 0, N);
		seg[v += N - 1] = 1;
		while (v > 0){
			v = v - 1 >> 1;
			b = v + v + 1;
			seg[v] = seg[b] + seg[++b];
		}
	}
	printf("%lld\n", ans);
	return (0);
}