Submission #762638

#	Time	Username	Problem	Language	Result	Execution time	Memory
762638		rainboy	Swap Swap Sort (CCO21_day1problem1)	C11	25 / 25	993 ms	53436 KiB

Main

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

#define N	100000
#define C	100
#define K	(N / C)

int *ei[N], eo[N];

void append(int a, int i) {
	int o = eo[a]++;

	if (o >= 2 && (o & o - 1) == 0)
		ei[a] = (int *) realloc(ei[a], o * 2 * sizeof *ei[a]);
	ei[a][o] = i;
}

int ft[N];

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 int aa[N], bb[N], gg[N];
	static long long xx[K][N];
	int n, m, q, g, h, i, a, b, k, o1, o2;
	long long ans;

	scanf("%d%d%d", &n, &m, &q);
	for (a = 0; a < n; a++)
		ei[a] = (int *) malloc(2 * sizeof *ei[a]);
	ans = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &a), a--;
		aa[i] = a, append(a, i);
		ans += query(m - 2 - a);
		update(m - 1 - a, m);
	}
	for (h = 0; h < m; h++)
		bb[h] = h;
	for (a = 0, g = 0; a < m; a++)
		if (eo[a] < C)
			gg[a] = -1;
		else {
			gg[a] = g;
			k = 0;
			for (i = 0; i < n; i++)
				if (aa[i] == a)
					k++;
				else
					xx[g][aa[i]] += k;
			g++;
		}
	while (q--) {
		scanf("%d", &h), h--;
		a = bb[h], b = bb[h + 1];
		if ((g = gg[a]) != -1)
			ans += xx[g][b] * 2 - (long long) eo[a] * eo[b];
		else if ((g = gg[b]) != -1)
			ans -= xx[g][a] * 2 - (long long) eo[a] * eo[b];
		else {
			ans -= (long long) eo[a] * eo[b];
			for (o1 = 0, o2 = 0; o2 < eo[b]; o2++) {
				while (o1 < eo[a] && ei[a][o1] < ei[b][o2])
					o1++;
				ans += o1 * 2;
			}
		}
		bb[h] = b, bb[h + 1] = a;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:43:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:48:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d", &a), a--;
      |   ^~~~~~~~~~~~~~~
Main.c:69:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d", &h), h--;
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 5 / 5
• Subtask 4: 14 / 14