QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#845201 | #1942. Another Substring Query Problem | ASnown | AC ✓ | 3071ms | 417248kb | C++17 | 4.3kb | 2025-01-06 15:21:52 | 2025-01-06 15:21:52 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
namespace asnown {
using i32=int32_t; using u32=uint32_t;
using i64=int64_t; using u64=uint64_t;
using i128=__int128_t; using u128=__uint128_t; };
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
constexpr i32 inverse(i32 a,i32 m) { i64 r=1;
for(;a>1;a=m%a) r=r*(m-m/a)%m; return r; }
template<i32 m>
class static_modint {
using mint=static_modint;
public:
constexpr static_modint() : v(0) {}
constexpr static_modint(i32 v) : v(normal(v%m)) {}
constexpr static_modint(u32 v) : v(v%m) {}
constexpr static_modint(i64 v) : v(normal(v%m)) {}
constexpr static_modint(u64 v) : v(v%m) {}
constexpr static_modint(i128 v) : v(normal(v%m)) {}
constexpr static_modint(u128 v) : v(v%m) {}
constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
constexpr u32 val() const { return v; }
constexpr static u32 mod() { return m; }
constexpr explicit operator bool() const { return v; }
constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
constexpr mint pow(i64 b) const { assert(b>=0);
mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint()-*this; }
constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
constexpr mint& operator++() { return (*this)+=1; }
constexpr mint& operator--() { return (*this)-=1; }
constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
constexpr bool operator==(const mint& p) const { return val()==p.val(); }
constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
const int P=1e9+7,B=131;
using hint=asnown::static_modint<P>;
const int N = 2e5+25;
int n,Q;
string s;
unordered_map<uint,int> bot;
unordered_map<uint,pair<int,vector<pair<int,int>>>> q;
int ans[N];
hint pw[N],h[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Solve();
}
void Solve() {
cin>>s,n=s.size(),s=' '+s;
pw[0]=1; for(int i=1;i<=n;i++) pw[i]=pw[i-1]*B;
vector<int> len;
cin>>Q;
for(int i=1;i<=Q;i++) {
string t; int k; cin>>t>>k;
len.emplace_back(t.size());
hint h=0;
for(auto ch:t) h=h*B+ch;
ans[i]=-1;
q[h.val()].second.emplace_back(k,i);
}
sort(ALL(len)),len.erase(unique(ALL(len)),len.end());
for(auto &[x,que]:q) sort(ALL(que.second)),que.first=0;
for(int i=1;i<=n;i++) {
h[i]=h[i-1]*B+s[i];
for(auto l:len) if(l<=i) {
hint H=h[i]-h[i-l]*pw[l];
++bot[H.val()];
int cnt=bot[H.val()];
auto &hh=q[H.val()].first;
auto &qry=q[H.val()].second;
for(;hh<qry.size()&&qry[hh].first==cnt;hh++)
ans[qry[hh].second]=i-l+1;
}
}
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2817ms
memory: 5824kb
input:
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...
output:
50997 112451 97534 13355 150562 5772 146250 10904 4343 194777 71395 96501 6809 18571 166901 114789 123587 176339 29660 82650 63509 80101 47907 66143 199971 108032 140518 49221 46212 28127 61461 149025 142818 33646 17132 196161 36671 28656 16860 141951 139429 72866 162807 21343 194803 16263 118701 20...
result:
ok 631 lines
Test #2:
score: 0
Accepted
time: 148ms
memory: 31620kb
input:
gnzlzbsarybaxilacuopvdkhjfiynrgfdhsrecyxedcrriztcxboczhfaseqglcwshaewaepasxqpaxxbroxndbxqabrvtrrshrnnlyfodtxyltjkbghfkjcqrqsuwdsgypcaroaojqbfrjqbdrimglxcqtfmqaeogqunaegfpfzcmyjwfgbwaigwitcyspiedbisjuedeyseneuzjdteifzvdfzhenapmmreqpvwsmtrxowjnmmrthzhojgxsoppfgfgohoghuwvqclzsmeydusfndrdyqokpqwupixyoxr...
output:
-1 -1 174057 -1 141370 -1 75407 -1 112842 -1 -1 4510 100584 12223 35161 28768 -1 5258 151196 -1 25061 87769 -1 135272 -1 -1 -1 159851 -1 -1 121971 108762 60263 143662 -1 5200 65515 -1 -1 -1 -1 157064 65499 -1 84122 173745 171855 -1 193921 -1 121426 162134 137032 126244 99210 155648 95498 151755 1105...
result:
ok 54751 lines
Test #3:
score: 0
Accepted
time: 48ms
memory: 8588kb
input:
gnzlzbsarybaxilacuopvdkhjfiynrgfdhsrecyxedcrriztcxboczhfaseqglcwshaewaepasxqpaxxbroxndbxqabrvtrrshrnnlyfodtxyltjkbghfkjcqrqsuwdsgypcaroaojqbfrjqbdrimglxcqtfmqaeogqunaegfpfzcmyjwfgbwaigwitcyspiedbisjuedeyseneuzjdteifzvdfzhenapmmreqpvwsmtrxowjnmmrthzhojgxsoppfgfgohoghuwvqclzsmeydusfndrdyqokpqwupixyoxr...
output:
-1 -1 -1 66435 197872 -1 83779 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 91584 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21808 -1 -1 -1 -1 -1 15575 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 196132 -...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 3071ms
memory: 417248kb
input:
qzpazeynjuulxowssvbghqhdtywsnzgwmpospvxyeoxsrwxccwucqgsyllrkburhfrivzqcpnevmixivrtbxexhrjauxayxmrdluzkvxnfvocgoceavurwlxzdfepcxzcdaoppzfhqpyhmjlhbfsntaewlfjqgefvqttczahgzgucgoohnjsdvyaxltixdvbgzoewptjuosymanxeiewbvnibhjbkhoebygmtmwldtvyijasjquxvtwkhlngbcremdsprdetxkggogyjbgsuduzmutcgblzoqopwspbzrurs...
output:
109498 154508 -1 -1 -1 -1 1028 36133 -1 -1 -1 -1 -1 191213 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 129366 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 196816 -1 -1 141983 -1 -1 137732 -1 11350 -1 -1 -1 25285 52189 -1 -1 -1 -1 80999 -1 -1 17773 5870 -1 -1 -1 -1 -1 128813 -1 1492 -1 -1 1513 -1 -1 -1 139760 199034 -1 -1 49122 ...
result:
ok 50034 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
dkfjahfwbaofboahsdlvkjnalsf 10 dkfjahfwbaofboahsdlvkjnalsfd 1 adkfjahfwbaofboahsdlvkjnalsf 1 kfj 2 kfj 1 a 3 a 1 a 2 a 4 w 2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 1
output:
-1 -1 -1 2 15 5 10 24 -1 -1
result:
ok 10 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
alfalfa 5 alfa 1 alfa 2 alfa 3 alfalfa 1 alfalfa 2
output:
1 4 -1 1 -1
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
x 28 a 1 b 1 c 1 d 1 e 1 f 1 g 1 h 1 i 1 j 1 k 1 l 1 m 1 n 1 o 1 p 1 q 1 r 1 s 1 t 1 u 1 v 1 w 1 x 1 y 1 z 1 abcdefghijklmnopqrstuvwxyz 1 abcdefghijklmnopqrstuvwxyz 1
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1
result:
ok 28 lines
Test #8:
score: 0
Accepted
time: 36ms
memory: 8496kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 6ms
memory: 6288kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
100001 -1
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 5ms
memory: 5496kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 5ms
memory: 5472kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 10ms
memory: 5728kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
1 1537 3073 5121 6145 7681 9217 10241 12289 13825 15361 17409 18433 20481 22017 23553 24577 26113 27649 29697 30721 32257 33793 34817 36865 38401 39937 40961 42497 44033 46081 47105 49153 50689 52225 54273 55297 56833 58369 59393 61441 62977 64513 66561 67585 69633 71169 72705 73729 75265 76801 7884...
result:
ok 195 lines