Submission #636560

#	Time	Username	Problem	Language	Result	Execution time	Memory
636560		rainboy	Misspelling (JOI22_misspelling)	C11	100 / 100	717 ms	238344 KiB

misspelling

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

#define N	500000
#define A	26
#define MD	1000000007

int *ej[N], *es[N], eo[N];

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

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		es[i] = (int *) realloc(es[i], o * 2 * sizeof *es[i]);
	}
	ej[i][o] = j, es[i][o] = s;
}

int main() {
	static int dp[N][A][2], dq[A], qu[2][N * A], cnt[2];
	int n, m, i, j, k, s, a, ka, o, x, ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		es[i] = (int *) malloc(2 * sizeof *es[i]);
	}
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		if (i < j)
			append(i, j, 0);
		else
			append(j, i, 1);
	}
	for (a = 0; a < A; a++)
		dp[n - 1][a][0] = 1, dq[a] = 1;
	for (i = n - 2; i >= 0; i--) {
		x = 0;
		for (a = 0; a < A; a++) {
			dp[i][a][0] = x;
			x = (x + dq[a]) % MD;
		}
		x = 0;
		for (a = A - 1; a >= 0; a--) {
			dp[i][a][1] = x;
			x = (x + dq[a]) % MD;
		}
		for (a = 0; a < A; a++)
			for (s = 0; s < 2; s++)
				qu[s][cnt[s]++] = i * A + a, dq[a] = (dq[a] + dp[i][a][s]) % MD;
		for (o = eo[i]; o--; ) {
			j = ej[i][o], s = es[i][o] ^ 1;
			while (cnt[s]) {
				ka = qu[s][cnt[s] - 1], k = ka / A, a = ka % A;
				if (k >= j)
					break;
				cnt[s]--, dq[a] = (dq[a] - dp[k][a][s] + MD) % MD;
				dp[k][a][s] = 0;
			}
		}
	}
	ans = 0;
	for (i = 0; i < n; i++)
		for (a = 0; a < A; a++)
			for (s = 0; s < 2; s++)
				ans = (ans + dp[i][a][s]) % MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11