Submission #636558

#	Time	Username	Problem	Language	Result	Execution time	Memory
636558		rainboy	Misspelling (JOI22_misspelling)	C11	28 / 100	4046 ms	149816 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];
	int n, m, i, j, k, s, a, 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++)
			dq[a] = ((long long) dq[a] + dp[i][a][0] + dp[i][a][1]) % MD;
		for (o = eo[i]; o--; ) {
			j = ej[i][o], s = es[i][o];
			for (k = i; k < j; k++)
				for (a = 0; a < A; a++) {
					dq[a] = (dq[a] - dp[k][a][s ^ 1] + MD) % MD;
					dp[k][a][s ^ 1] = 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: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11