Submission #67458763

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define MAX 8192
int bit_table[MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos++;
  while (pos > 0) {
    sum += bit_table[pos - 1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#define MAX 8192

int bit_table[MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos++;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int N;
int A[MAX];

struct youso_s {
	int value, idx;
};

int cmp(const void* x, const void* y) {
	struct youso_s a = *(const struct youso_s*)x, b = *(const struct youso_s*)y;
	return a.value < b.value ? -1 : a.value > b.value;
}

struct youso_s youso[MAX];

int main(void) {
	int i, j, k;
	int64_t ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
		youso[i].value = A[i];
		youso[i].idx = i;
	}
	/* 下から処理する */
	qsort(youso, N, sizeof(*youso), cmp);
	for (i = 0; i < N; ) {
		/* 同じ高さのやつをまとめて処理する */
		for (j = i; j < N && youso[j].value == youso[i].value; j++) {
			/* これまでのやつ (すなわち、これより小さい) の数を前後に分けて求める */
			int pos = youso[j].idx;
			int mae = bit_sum(pos);
			int ato = bit_sum(N) - mae;
			ans += (int64_t)mae * ato;
		}
		/* この高さのやつを仲間に加える */
		for (k = i; k < j; k++) {
			bit_add(youso[k].idx, 1);
		}
		i = j;
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

Submission Info

Judge Result