oj.uz

Submission #762638

# Submission time Handle Problem Language Result Execution time Memory
762638 2023-06-21T15:13:24 Z rainboy Swap Swap Sort (CCO21_day1problem1) C
25 / 25
 993 ms 53436 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5296 KB Output is correct
2 Correct 14 ms 5420 KB Output is correct
3 Correct 20 ms 6092 KB Output is correct
4 Correct 52 ms 12316 KB Output is correct
5 Correct 14 ms 5768 KB Output is correct
6 Correct 16 ms 5720 KB Output is correct
7 Correct 15 ms 6036 KB Output is correct
8 Correct 15 ms 6704 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 18212 KB Output is correct
2 Correct 184 ms 18336 KB Output is correct
3 Correct 197 ms 19112 KB Output is correct
4 Correct 202 ms 19960 KB Output is correct
5 Correct 234 ms 23828 KB Output is correct
6 Correct 252 ms 25000 KB Output is correct
7 Correct 255 ms 25072 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 10 ms 5296 KB Output is correct
10 Correct 14 ms 5420 KB Output is correct
11 Correct 20 ms 6092 KB Output is correct
12 Correct 52 ms 12316 KB Output is correct
13 Correct 14 ms 5768 KB Output is correct
14 Correct 16 ms 5720 KB Output is correct
15 Correct 15 ms 6036 KB Output is correct
16 Correct 15 ms 6704 KB Output is correct
17 Correct 182 ms 18212 KB Output is correct
18 Correct 184 ms 18336 KB Output is correct
19 Correct 197 ms 19112 KB Output is correct
20 Correct 202 ms 19960 KB Output is correct
21 Correct 234 ms 23828 KB Output is correct
22 Correct 252 ms 25000 KB Output is correct
23 Correct 255 ms 25072 KB Output is correct
24 Correct 481 ms 27304 KB Output is correct
25 Correct 757 ms 20952 KB Output is correct
26 Correct 451 ms 21560 KB Output is correct
27 Correct 348 ms 21584 KB Output is correct
28 Correct 297 ms 22220 KB Output is correct
29 Correct 268 ms 22752 KB Output is correct
30 Correct 265 ms 23532 KB Output is correct
31 Correct 256 ms 23444 KB Output is correct
32 Correct 213 ms 32320 KB Output is correct
33 Correct 268 ms 23880 KB Output is correct
34 Correct 238 ms 25004 KB Output is correct
35 Correct 251 ms 26604 KB Output is correct
36 Correct 482 ms 26940 KB Output is correct
37 Correct 774 ms 21384 KB Output is correct
38 Correct 603 ms 21368 KB Output is correct
39 Correct 278 ms 23476 KB Output is correct
40 Correct 298 ms 29876 KB Output is correct
41 Correct 249 ms 37704 KB Output is correct
42 Correct 268 ms 39464 KB Output is correct
43 Correct 244 ms 47340 KB Output is correct
44 Correct 242 ms 51856 KB Output is correct
45 Correct 257 ms 53436 KB Output is correct
46 Correct 385 ms 23372 KB Output is correct
47 Correct 513 ms 23332 KB Output is correct
48 Correct 993 ms 24304 KB Output is correct
49 Correct 805 ms 23448 KB Output is correct
50 Correct 237 ms 31544 KB Output is correct
51 Correct 234 ms 31760 KB Output is correct
52 Correct 224 ms 31732 KB Output is correct
53 Correct 236 ms 30792 KB Output is correct
54 Correct 227 ms 30804 KB Output is correct
55 Correct 0 ms 212 KB Output is correct