Submission #70579329

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 <inttypes.h>
#define BIT_MAX 312345
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos++;
  while (pos <= BIT_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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define BIT_MAX 312345

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos++;
	while (pos <= BIT_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[BIT_MAX];

int main(void) {
	int i;
	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;
	}
	for (i = N - 1; i >= 0; i--) {
		ans += bit_sum(a[i]);
		bit_add(a[i], 1);
	}
	for (i = 0; i < N; i++) {
		printf("%" PRId64 "\n", ans);
		/* 先頭の要素を最後に持っていくので */
		/* 先頭の要素より小さい要素の個数だけ減る */
		ans -= a[i];
		/* 先頭の要素より大きい要素の個数だけ増える */
		ans += N - a[i] - 1;
	}
	return 0;
}

Submission Info

Judge Result