提出 0fd96763-ba54-461f-ae96-c96fdced531a

コード

#ifndef INCLUDE_MACRO
#define INCLUDE_MACRO
#include __FILE__

int solve() {
    
    return 0;
}

using mint = modint998244353;
const int INV_26 = mod_pow(26LL, MOD - 2, MOD);
using mint10 = static_modint<1000000009>;
const int MOD10 = 1'000'000'009LL;
const int INV_2610 = mod_pow(26LL, MOD10 - 2, MOD10);

signed main() {
    int n;
    cin >> n;
    vector<pair<char, int>> s(n);
    rep(i, n) cin >> s[i].first >> s[i].second;
    int m;
    cin >> m;
    vector<pair<char, int>> t(m);
    rep(i, m) cin >> t[i].first >> t[i].second;
    if (n < m) {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    if (m == 1) {
        rep(i, n) {
            if (s[i].first == t[0].first && 
            s[i].second >= t[0].second) ans += s[i].second - t[0].second + 1;
        }
    }else if (m == 2) {
        rep(i, n - 1) {
            if (s[i].first == t[0].first && 
            s[i + 1].first == t.back().first && 
            s[i].second >= t[0].second && 
            s[i + 1].second >= t.back().second) ans++;
        }
    }else {
        // 1~m-2をhash!!!
        mint beki26 = 1;
        mint10 beki2610 = 1;
        mint s_hash = 0;
        mint10 s_hash10 = 0;
        mint s_hash_num = 0;
        mint10 s_hash_num10 = 0;
        mint t_hash = 0;
        mint10 t_hash10 = 0;
        mint t_hash_num = 0;
        mint10 t_hash_num10 = 0;
        for (int i = 1; i < m - 1; i++) {
            s_hash += (s[i].first - 'a') * beki26;
            s_hash10 += (s[i].first - 'a') * beki2610;
            s_hash_num += s[i].second % MOD * beki26;
            s_hash_num10 += s[i].second % MOD10 * beki2610;
            t_hash += (t[i].first - 'a') * beki26;
            t_hash10 += (t[i].first - 'a') * beki2610;
            t_hash_num += t[i].second % MOD * beki26;
            t_hash_num10 += t[i].second % MOD10 * beki2610;
            if (i != m - 2) beki26 *= 26;
            if (i != m - 2) beki2610 *= 26;
        }
        if (s_hash == t_hash && s_hash10 == t_hash10) {
            int check_l = 0;
            int check_r = m - 1;
            if (t[0].first == s[check_l].first && 
            t.back().first == s[check_r].first && 
            s[check_l].second >= t[0].second && 
            s[check_r].second >= t.back().second) {
                if (s_hash_num == t_hash_num && s_hash_num10 == t_hash_num10) ans++;
            }
        }
        for (int i = m - 1; i < n - 1; i++) {
            s_hash -= (s[i - (m - 2)].first - 'a');
            s_hash10 -= (s[i - (m - 2)].first - 'a');
            s_hash_num -= s[i - (m - 2)].second % MOD;
            s_hash_num10 -= s[i - (m - 2)].second % MOD10;
            s_hash *= INV_26;
            s_hash10 *= INV_2610;
            s_hash_num *= INV_26;
            s_hash_num10 *= INV_2610;
            s_hash += (s[i].first - 'a') * beki26;
            s_hash10 += (s[i].first - 'a') * beki2610;
            s_hash_num += s[i].second % MOD * beki26;
            s_hash_num10 += s[i].second % MOD10 * beki2610;
            if (s_hash == t_hash && s_hash10 == t_hash10) {
                int check_l = 0 + i - (m - 2);
                int check_r = m - 1 + i - (m - 2);
                if (t[0].first == s[check_l].first && 
                t.back().first == s[check_r].first && 
                s[check_l].second >= t[0].second && 
                s[check_r].second >= t.back().second) {
                    if (s_hash_num == t_hash_num && s_hash_num10 == t_hash_num10) ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

#else

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define int long long
#define under(N) std::fixed << std::setprecision(N)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rep(i, n) for (int i = 0; i < n; i++)
#define orep(i, n) for (int i = 1; i <= n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define cy std::cout << "Yes" << std::endl
#define cyre {std::cout << "Yes" << std::endl; return 0;}
#define cn std::cout << "No" << std::endl
#define cnre {std::cout << "No" << std::endl; return 0;}
#define MOD 998244353LL
#define INF (3LL<<60)
#define PI 3.141592653589793238
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
std::vector<int> dx = {1, -1, 0, 0};
std::vector<int> dy = {0, 0, 1, -1};
std::vector<int> dx8 = {1, -1, 0, 0, 1, -1, -1, 1};
std::vector<int> dy8 = {0, 0, 1, -1, 1, -1, 1, -1};
template<class T>
T ipow(T x, T y) {
    T ret = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            ret *= x;
        }
        x *= x;
        y >>= 1;
    }
    return ret;
}
template<class T>
T mod_pow(T x, T y, T mod) {
    T ret = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            ret = ret * x % mod;
        }
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
template<class T>
T isqrt(T n) {
    if (n == 0) return 0;
    T rinzi = T(std::sqrt(n)) - 1;
    return rinzi * (rinzi + 2) < n ? rinzi + 1 : rinzi;
}
template<class T>
bool out_glid(T i, T j, T h, T w) {
    if (i < 0 || h <= i || j < 0 || w <= j) return true;
    else return false;
}
void allout(vector<int> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << *it;
        if (it != prev(x.end())) std::cout << " ";
    }
    std::cout << std::endl;
}
void allout(vector<string> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << *it << std::endl;
    }
}
void allout(vector<bool> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        if (*it) std::cout << 1;
        else std::cout << 0;
        if (it != prev(x.end())) std::cout << " ";
    }
    std::cout << std::endl;
}
void allout(vector<pair<int, int>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " " << it->second << endl;
    }
}
template<class T>
void allout(vector<vector<T>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        allout(*it);
    }
}
void allout(set<int> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << *it;
        if (it != prev(x.end())) std::cout << " ";
    }
    std::cout << std::endl;
}
void allout(set<pair<int, int>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " " << it->second << endl;
    }
}
template<class T>
void allout(vector<set<T>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        allout(*it);
    }
}
void allout(map<int, int> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " : " << it->second << std::endl;
    }
}
void allout(map<int, pair<int, int>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " : " << (it->second).first << " " << (it->second).second << std::endl;
    }
}
template<class T>
void allout(map<int, vector<T>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " : ";
        allout(it->second);
    }
}
template<class T>
void allout(map<int, set<T>> &x) {
    for (auto it = x.begin(); it != x.end(); it++) {
        std::cout << it->first << " : ";
        allout(it->second);
    }
}
class Timer {
    chrono::system_clock::time_point start;
public:
    Timer() : start(chrono::system_clock::now()) {}
    double count() {
        chrono::duration<double> Time_ = chrono::system_clock::now() - start;
        return Time_.count();
    }
    bool is_under(double x) {
        return (this->count()) < x;
    }
};

#endif

結果

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

テストセット

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

詳細結果

テストケース	結果	実行時間	メモリ
1_1	AC	19 ms	8320 KiB
1_2	AC	18 ms	8320 KiB
1_3	AC	16 ms	8320 KiB
1_4	AC	19 ms	8320 KiB
1_5	AC	18 ms	8064 KiB
1_6	AC	17 ms	8192 KiB
2_1	AC	16 ms	8192 KiB
2_2	AC	16 ms	8320 KiB
2_3	AC	18 ms	8576 KiB
2_4	AC	17 ms	8192 KiB
2_5	AC	18 ms	8320 KiB
2_6	AC	19 ms	8192 KiB
3_1	AC	19 ms	8448 KiB
3_2	AC	17 ms	8192 KiB
3_3	AC	21 ms	8064 KiB
3_4	AC	19 ms	8320 KiB
3_5	AC	19 ms	8320 KiB
3_6	AC	18 ms	8192 KiB
4_1	AC	20 ms	8320 KiB
4_2	AC	59 ms	8192 KiB
4_3	AC	17 ms	8448 KiB
4_4	AC	17 ms	8320 KiB
4_5	AC	19 ms	8064 KiB
4_6	AC	19 ms	8320 KiB
5_1	AC	181 ms	8320 KiB
5_10	AC	166 ms	8320 KiB
5_2	AC	129 ms	8064 KiB
5_21	WA	440 ms	7936 KiB
5_3	AC	31 ms	8064 KiB
5_4	AC	115 ms	8576 KiB
5_5	AC	104 ms	8448 KiB
5_6	AC	127 ms	8192 KiB
5_7	AC	147 ms	8192 KiB
5_8	AC	21 ms	8320 KiB
5_9	AC	344 ms	8320 KiB
sample_1	AC	17 ms	8192 KiB
sample_2	AC	16 ms	8320 KiB
sample_3	AC	18 ms	8320 KiB