Submission #503344

#	Time	Username	Problem	Language	Result	Execution time	Memory
503344		rainboy	Ekoeko (COCI21_ekoeko)	C11	110 / 110	8 ms	2592 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	100000
#define A	26

int ft[N * 2];

void update(int i, int n) {
	while (i < n) {
		ft[i]++;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static char cc[N * 2 + 1];
	static int kk[A], hh[A], ii[N * 2], aa[N * 2], rr[N * 2];
	int n, h, h_, i, k, a;
	long long ans;

	scanf("%d%s", &n, cc);
	for (i = 0; i < n * 2; i++)
		kk[cc[i] - 'a']++;
	for (a = 1; a < A; a++)
		hh[a] = hh[a - 1] + kk[a - 1];
	for (i = 0; i < n * 2; i++)
		ii[aa[i] = hh[cc[i] - 'a']++] = i;
	memset(rr, -1, n * 2 * sizeof *rr);
	for (a = 0, h = 0; a < A; h += kk[a], a++)
		for (h_ = h; h_ < h + kk[a] / 2; h_++)
			rr[ii[h_]] = ii[h_ + kk[a] / 2];
	ans = 0;
	for (i = n * 2 - 1, k = 0; i >= 0; i--)
		if (rr[i] != -1)
			k++;
		else
			ans += k;
	for (i = n * 2 - 1, k = 0; i >= 0; i--)
		if (rr[i] != -1) {
			ans += query(rr[i] - 1);
			update(rr[i], n * 2);
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40