Submission #832325

#	Time	Username	Problem	Language	Result	Execution time	Memory
832325		rainboy	Dabbeh (INOI20_dabbeh)	C11	100 / 100	300 ms	112584 KiB

Main

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

#define N	300000
#define M	10000
#define L	500000
#define N_	(L + 2)
#define A	26

int tt[N_][A], ff_[N_][A], ff[N_], dd[N_], n_;

void build(char **ccc, int m) {
	static int qu[N_];
	int cnt, l, g, h, a, s, t, e, f;

	n_ = 2;
	dd[0] = -1, dd[1] = 0;
	for (h = 0; h < m; h++) {
		l = strlen(ccc[h]);
		for (g = 0, s = 1; g < l; g++) {
			a = ccc[h][g] - 'a';
			if (!tt[s][a])
				dd[tt[s][a] = n_++] = g + 1;
			s = tt[s][a];
		}
	}
	cnt = 0;
	for (a = 0; a < A; a++)
		tt[0][a] = 1, ff_[0][a] = 0;
	ff[1] = 0, qu[cnt++] = 1;
	for (h = 0; h < cnt; h++) {
		s = qu[h], e = ff[s];
		for (a = 0; a < A; a++) {
			t = tt[s][a], f = tt[e][a];
			if (t == 0)
				tt[s][a] = f, ff_[s][a] = s;
			else
				ff_[s][a] = ff_[e][a], ff[t] = f, qu[cnt++] = t;
		}
	}
}

int main() {
	static char aa[N + 1], bb[L + 1], *ccc[M], rank[N + 1];
	static int rr[N + 1], jj[N + 1], jj_[N + 1], qu[N + 1];
	int n, m, q, cnt, h, i, j, a, s, t, lower, upper;

	scanf("%d%d", &m, &q);
	for (h = 0; h < m; h++) {
		scanf("%s", bb);
		ccc[h] = strdup(bb);
	}
	scanf("%s", aa), n = strlen(aa);
	build(ccc, m);
	for (i = 0, s = 1; i < n; i++) {
		a = aa[i] - 'a';
		for (t = s; t = ff_[t][a]; t = ff[t])
			rr[i - dd[t]] = i;
		s = tt[s][a];
	}
	while (dd[s] >= 0)
		rr[n - dd[s]] = n, s = ff[s];
	cnt = 0;
	for (i = n; i >= 0; i--) {
		while (cnt && rr[qu[cnt - 1]] <= rr[i])
			cnt--;
		qu[cnt++] = i;
		lower = -1, upper = cnt - 1;
		while (upper - lower > 1) {
			h = (lower + upper) / 2;
			if (qu[h] <= rr[i])
				upper = h;
			else
				lower = h;
		}
		jj[i] = qu[upper];
		if (i == jj[i])
			jj_[i] = jj[i], rank[i] = 0;
		else if (rank[jj[i]] == rank[jj_[jj[i]]])
			jj_[i] = jj_[jj_[jj[i]]], rank[i] = rank[jj[i]] + 1;
		else
			jj_[i] = jj[i], rank[i] = 1;
	}
	while (q--) {
		int k;

		scanf("%d%d", &i, &j);
		k = 1;
		while (rr[i] < j) {
			if (i == jj[i]) {
				k = -1;
				break;
			}
			if (rr[jj_[i]] < j)
				k += (1 << rank[i]) - 1, i = jj_[i];
			else
				k++, i = jj[i];
		}
		printf("%d\n", k);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:57:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   57 |   for (t = s; t = ff_[t][a]; t = ff[t])
      |               ^
Main.c:48:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d", &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:50:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%s", bb);
      |   ^~~~~~~~~~~~~~~
Main.c:53:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%s", aa), n = strlen(aa);
      |  ^~~~~~~~~~~~~~~
Main.c:87:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d", &i, &j);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50