Submission #503338

#	Time	Username	Problem	Language	Result	Execution time	Memory
503338		rainboy	Ekoeko (COCI21_ekoeko)	C11	30 / 110	1086 ms	2432 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, a, subtask1;
	long long ans;

	scanf("%d%s", &n, cc);
	subtask1 = 1;
	for (i = 0; i < n * 2; i++)
		if (cc[i] != (i < n ? 'a' : 'b')) {
			subtask1 = 0;
			break;
		}
	if (subtask1) {
		printf("%lld\n", (long long) n * n / 4);
		return 0;
	}
	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 - 1; i >= 0; i--) {
		ans += query(rr[i] - n - 1);
		update(rr[i] - n, n);
	}
	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: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40