提出 673d67f4-d7d7-4e5a-986a-2cc4e275f947

コード

#include <bits/stdc++.h>
#include <atcoder/string>
using atcoder::z_algorithm;
using namespace std;
using ll = long long;

using P = pair<char, ll>;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, M;
	cin >> N;

	vector<P> S(N);
	for (int i = 0; i < N; i++)
	{
		cin >> S[i].first >> S[i].second;
	}
	cin >> M;
	vector<P> G(M);
	for (int i = 0; i < M; i++)
	{
		cin >> G[i].first >> G[i].second;
	}

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

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

	// 中間
	vector<P> pattern;
	for (int i = 1; i < M - 1; i++)
	{
		pattern.push_back(G[i]);
	}

	vector<P> concat = pattern;
	concat.emplace_back('#', -1);
	for (auto &x : S)
		concat.push_back(x);

	auto z = z_algorithm(concat);

	int K = pattern.size();
	ll ans = 0;

	for (int i = 0; i < N; i++)
	{
		if (S[i].first != G[0].first || S[i].second < G[0].second)
			continue;

		int zpos = K + 1 + i;
		if (z[zpos] < K)
			continue;

		int j = i + K + 1;
		if (j >= N)
			continue;

		if (S[j].first == G[M - 1].first &&
			S[j].second >= G[M - 1].second)
		{
			ans++;
		}
	}

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

結果

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

テストセット

テストセット	結果	得点	実行時間	メモリ
Sample	AC × 2 WA × 1	0	15 ms	8320 KiB
Subtask1	AC × 7	5	15 ms	8448 KiB
Subtask2	AC × 6 WA × 3	0	15 ms	8320 KiB
Subtask3	AC × 10 WA × 5	0	15 ms	8320 KiB
Subtask4	AC × 15 WA × 6	0	15 ms	8448 KiB
Subtask5	AC × 26 WA × 11	0	74 ms	13536 KiB

詳細結果

テストケース	結果	実行時間	メモリ
1_1	AC	14 ms	8064 KiB
1_2	AC	13 ms	8448 KiB
1_3	AC	14 ms	8192 KiB
1_4	AC	14 ms	8320 KiB
1_5	AC	15 ms	8448 KiB
1_6	AC	15 ms	8320 KiB
2_1	AC	14 ms	8192 KiB
2_2	AC	14 ms	8064 KiB
2_3	WA	15 ms	8064 KiB
2_4	AC	15 ms	8064 KiB
2_5	WA	13 ms	8064 KiB
2_6	AC	14 ms	8192 KiB
3_1	AC	13 ms	8320 KiB
3_2	AC	13 ms	8320 KiB
3_3	AC	14 ms	7936 KiB
3_4	WA	14 ms	8192 KiB
3_5	WA	14 ms	8192 KiB
3_6	AC	14 ms	8192 KiB
4_1	AC	13 ms	8192 KiB
4_2	AC	14 ms	8448 KiB
4_3	AC	14 ms	8064 KiB
4_4	WA	14 ms	8192 KiB
4_5	AC	13 ms	8064 KiB
4_6	AC	14 ms	8064 KiB
5_1	AC	26 ms	8064 KiB
5_10	WA	33 ms	9700 KiB
5_2	AC	19 ms	8064 KiB
5_3	AC	22 ms	8192 KiB
5_4	WA	18 ms	8192 KiB
5_5	AC	33 ms	8448 KiB
5_6	AC	45 ms	13536 KiB
5_7	WA	74 ms	12532 KiB
5_8	WA	23 ms	8320 KiB
5_9	WA	42 ms	8320 KiB
sample_1	AC	15 ms	8320 KiB
sample_2	AC	13 ms	8192 KiB
sample_3	WA	13 ms	8320 KiB