QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845297#1942. Another Substring Query ProblemlfyszyTL 0ms0kbC++201.4kb2025-01-06 15:49:192025-01-06 15:49:28

Judging History

This is the latest submission verdict.

  • [2025-01-06 15:49:28]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2025-01-06 15:49:19]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define SP << " " <<
#define fish signed
using namespace std;
mt19937 rnd(1209);
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10, mod = 998244353, base = 66683;
int h[N], p[N];
int get(int l, int r) {return ((h[r] - h[l - 1] * p[r - l + 1] % mod) % mod + mod) % mod;}
map<pair<int, int>, int> mp;
unordered_map<int, int> nt;
set<int> len;
pair<int, int> qe[N];
fish main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s; cin >> s; s = 'Y' + s;
    p[0] = 1;
    for(int i = 1; s[i]; i ++) h[i] = (h[i - 1] * base % mod + (int)s[i]) % mod, p[i] = p[i - 1] * base % mod;
    int m; cin >> m;
    for(int i = 1; i <= m; i ++)
    {
        int k; string t; cin >> t >> k;
        int hs = 0;
        for(auto ch : t) hs = (hs * base % mod + (int)ch) % mod;
        qe[i] = {hs, k};
        len.insert(t.size());
    }
    for(int i = 1; s[i]; i ++)
    {
        for(auto v : len)
        {
            int now = get(i, i + v - 1);
            nt[now] ++; mp[{now, nt[now]}] = i;
        }
    }
    for(int i = 1; i <= m; i ++)
    {
        if(!mp.count(qe[i])) cout << "-1\n";
        else cout << mp[qe[i]] << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

output:


result: