Submission #823351

#	Time	Username	Problem	Language	Result	Execution time	Memory
823351		rainboy	Line Town (CCO23_day1problem3)	C11	25 / 25	181 ms	23880 KiB

Main

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

#define N	500000
#define INF	0x3f3f3f3f3f3f3f3fLL

int abs_(int a) { return a > 0 ? a : -a; }
long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N];

int compare(int i, int j) {
	int ai = abs_(aa[i]), aj = abs_(aa[j]);

	if (ai != aj)
		return aj - ai;
	if (aa[i] != aa[j])
		return aa[i] - aa[j];
	return i - j;
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

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 ii[N], ii1[N], ii2[N], kkp1[N + 1], kkp2[N + 1], kkq1[N + 1], kkq2[N + 1];
	static long long dp[2], dq[2], vvp[N + 1], vvq[N + 1];
	int n, n0, n1, n2, h, h_, h1, r, s, i, k, k1, k2, l1, l2, a;
	long long v, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		if (i % 2 != 0)
			aa[i] = -aa[i];
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	memset(dp, 0x3f, sizeof dp), dp[0] = 0;
	for (h = 0; h < n; h = h_) {
		a = abs_(aa[ii[h]]);
		if (a == 0)
			break;
		h_ = h, n1 = 0;
		while (h_ < n && aa[i = ii[h_]] == -a)
			ii1[n1++] = i - query(i), h_++;
		n2 = 0;
		while (h_ < n && aa[i = ii[h_]] == a)
			ii2[n2++] = i - query(i), h_++;
		n0 = n - h_;
		for (h1 = h; h1 < h_; h1++)
			update(ii[h1], n);
		memset(dq, 0x3f, sizeof dq);
		for (r = 0; r < 2; r++) {
			if (dp[r] == INF)
				continue;
			kkp1[0] = k1 = 0, kkp2[0] = k2 = 0, vvp[0] = v = 0;
			for (k = 1, l1 = 0, l2 = 0; k <= n1 + n2; k++) {
				if ((k - 1) % 2 == r) {
					if (k1 < n1) {
						i = ii1[k1];
						while (l2 < n2 && ii2[l2] < i)
							l2++;
						v += i - k1 - min(l2, k2);
					}
					k1++;
				} else {
					if (k2 < n2) {
						i = ii2[k2];
						while (l1 < n1 && ii1[l1] < i)
							l1++;
						v += i - k2 - min(l1, k1);
					}
					k2++;
				}
				kkp1[k] = k1, kkp2[k] = k2, vvp[k] = v;
			}
			kkq1[n1 + n2] = k1 = n1, kkq2[n1 + n2] = k2 = n2, vvq[n1 + n2] = v = 0;
			for (k = n1 + n2 - 1, l1 = n1, l2 = n2; k >= 0; k--) {
				if ((n0 + k) % 2 != r) {
					k1--;
					if (k1 >= 0) {
						i = ii1[k1];
						while (l2 > 0 && ii2[l2 - 1] >= i)
							l2--;
						v += n0 - (i - k1 - l2) + max(l2 - k2, 0);
					}
				} else {
					k2--;
					if (k2 >= 0) {
						i = ii2[k2];
						while (l1 > 0 && ii1[l1 - 1] >= i)
							l1--;
						v += n0 - (i - k2 - l1) + max(l1 - k1, 0);
					}
				}
				kkq1[k] = k1, kkq2[k] = k2, vvq[k] = v;
			}
			for (k = 0; k <= n1 + n2; k++)
				if (kkp1[k] == kkq1[k] && kkp2[k] == kkq2[k]) {
					s = (r + k) % 2;
					dq[s] = min(dq[s], dp[r] + vvp[k] + vvq[k]);
				}
		}
		memcpy(dp, dq, sizeof dq);
	}
	ans = min(dp[0], dp[1]);
	if (ans == INF)
		ans = -1;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 3 / 3
• Subtask 7: 2 / 2
• Subtask 8: 3 / 3