QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845297 | #1942. Another Substring Query Problem | lfyszy | TL | 0ms | 0kb | C++20 | 1.4kb | 2025-01-06 15:49:19 | 2025-01-06 15:49:28 |
Judging History
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...