Submission #1073011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073011		rainboy	Heavy Light Decomposition (CCO24_day2problem2)	C11	25 / 25	607 ms	34208 KiB

Main

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

#define N	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define MD	1000003

int min(int a, int b) { return a < b ? a : b; }

int ss[2][N_ * 2], qq[2][N_ * 2], xx[2][N_ * 2], n_, t;

void pul(int i) {
	int l = i << 1, r = l | 1, ql, qr;

	ss[t][i] = ss[t][l] + ss[t][r];
	ql = qq[t][l] + ss[t][r], qr = qq[t][r];
	if (ql < qr)
		qq[t][i] = ql, xx[t][i] = xx[t][l];
	else if (ql > qr)
		qq[t][i] = qr, xx[t][i] = xx[t][r];
	else
		qq[t][i] = ql, xx[t][i] = (xx[t][l] + xx[t][r]) % MD;
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update_x(int i, int x) {
	i += n_;
	xx[t][i] = x, pull(i);
}

void update_d(int i, int d) {
	i += n_;
	qq[t][i] = ss[t][i] += d, pull(i);
}

int main() {
	static int ii[N], pp[N], dp[N + 1];
	int n, i, j, a;

	scanf("%d", &n);
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	dp[0] = 1;
	for (t = 0; t < 2; t++)
		update_x(0, dp[0]);
	memset(ii, -1, n * sizeof *ii);
	for (j = 0; j < n; j++) {
		scanf("%d", &a), a--;
		pp[j] = i = ii[a], ii[a] = j;
		for (t = 0; t < 2; t++) {
			if (j % 2 == t) {
				if (i != -1)
					update_d(i, 1);
			} else {
				update_d(j, 1);
				if (i != -1 && i % 2 != t) {
					update_d(i, -2);
					if (pp[i] != -1)
						update_d(pp[i], 1);
				}
			}
			dp[j + 1] = (dp[j + 1] + xx[t][1]) % MD;
		}
		for (t = 0; t < 2; t++)
			update_x(j + 1, dp[j + 1]);
	}
	printf("%d\n", dp[n]);
	return 0;
}

Compilation message (stderr)

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

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