提出 4da0d486-c2c4-44ca-b29c-2d8f278df59a

コード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Block
{
	char c;
	long long len;
	bool operator==(const Block &o) const
	{
		return c == o.c && len == o.len;
	}
	bool operator!=(const Block &o) const
	{
		return !(*this == o);
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	if (!(cin >> N))
		return 0;

	vector<Block> S(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> S[i].c >> S[i].len;
	}

	int M;
	cin >> M;
	vector<Block> G(M);
	for (int i = 0; i < M; ++i)
	{
		cin >> G[i].c >> G[i].len;
	}

	if (M == 1)
	{
		long long ans = 0;
		for (int i = 0; i < N; ++i)
		{
			if (S[i].c == G[0].c && S[i].len >= G[0].len)
			{
				ans += S[i].len - G[0].len + 1;
			}
		}
		cout << ans << "\n";
		return 0;
	}

	if (M == 2)
	{
		long long ans = 0;
		for (int i = 0; i + 1 < N; ++i)
		{
			if (S[i].c == G[0].c && S[i].len >= G[0].len &&
				S[i + 1].c == G[1].c && S[i + 1].len >= G[1].len)
			{
				ans++;
			}
		}
		cout << ans << "\n";
		return 0;
	}

	vector<Block> pattern(G.begin() + 1, G.end() - 1);
	int P = pattern.size();

	vector<int> lps(P, 0);
	for (int i = 1, len = 0; i < P;)
	{
		if (pattern[i] == pattern[len])
		{
			lps[i++] = ++len;
		}
		else
		{
			if (len != 0)
				len = lps[len - 1];
			else
				lps[i++] = 0;
		}
	}

	long long ans = 0;
	for (int i = 0, j = 0; i < N;)
	{
		if (S[i] == pattern[j])
		{
			i++;
			j++;
		}
		if (j == P)
		{
			int start_idx = i - P;
			int end_idx = i - 1;

			if (start_idx - 1 >= 0 && end_idx + 1 < N)
			{
				if (S[start_idx - 1].c == G[0].c && S[start_idx - 1].len >= G[0].len &&
					S[end_idx + 1].c == G.back().c && S[end_idx + 1].len >= G.back().len)
				{
					ans++;
				}
			}
			j = lps[j - 1];
		}
		else if (i < N && S[i] != pattern[j])
		{
			if (j != 0)
				j = lps[j - 1];
			else
				i++;
		}
	}

	cout << ans << "\n";
	return 0;
}

結果

問題	点数	言語	結果	実行時間	メモリ
D2. Substri18ng	270	C++ (gcc)	WA	269 ms	11136 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
Sample	AC × 3	0	12 ms	8320 KiB
Subtask1	AC × 7	5	12 ms	8576 KiB
Subtask2	AC × 9	100	12 ms	8448 KiB
Subtask3	AC × 15	95	12 ms	8576 KiB
Subtask4	AC × 21	70	29 ms	8576 KiB
Subtask5	AC × 37	0	269 ms	11136 KiB

詳細結果

テストケース	結果	実行時間	メモリ
1_1	AC	12 ms	8448 KiB
1_2	AC	11 ms	8192 KiB
1_3	AC	12 ms	8576 KiB
1_4	AC	12 ms	8192 KiB
1_5	AC	12 ms	8192 KiB
1_6	AC	12 ms	8448 KiB
2_1	AC	12 ms	8448 KiB
2_2	AC	11 ms	8192 KiB
2_3	AC	11 ms	8448 KiB
2_4	AC	11 ms	8320 KiB
2_5	AC	11 ms	8448 KiB
2_6	AC	11 ms	8320 KiB
3_1	AC	11 ms	8192 KiB
3_2	AC	11 ms	8448 KiB
3_3	AC	12 ms	7936 KiB
3_4	AC	11 ms	8192 KiB
3_5	AC	12 ms	8576 KiB
3_6	AC	12 ms	8320 KiB
4_1	AC	11 ms	8192 KiB
4_2	AC	11 ms	8448 KiB
4_3	AC	13 ms	8192 KiB
4_4	AC	11 ms	8320 KiB
4_5	AC	12 ms	8192 KiB
4_6	AC	29 ms	8064 KiB
5_1	AC	70 ms	8448 KiB
5_10	AC	61 ms	8320 KiB
5_2	AC	32 ms	8320 KiB
5_21	WA	269 ms	9984 KiB
5_3	AC	14 ms	8320 KiB
5_4	AC	51 ms	8064 KiB
5_5	AC	23 ms	8192 KiB
5_6	AC	47 ms	8320 KiB
5_7	AC	91 ms	8064 KiB
5_8	AC	12 ms	8192 KiB
5_9	AC	50 ms	11136 KiB
sample_1	AC	12 ms	8320 KiB
sample_2	AC	11 ms	8320 KiB
sample_3	AC	12 ms	8320 KiB