QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845201#1942. Another Substring Query ProblemASnownAC ✓3071ms417248kbC++174.3kb2025-01-06 15:21:522025-01-06 15:21:52

Judging History

This is the latest submission verdict.

  • [2025-01-06 15:21:52]
  • Judged
  • Verdict: AC
  • Time: 3071ms
  • Memory: 417248kb
  • [2025-01-06 15:21:52]
  • Submitted

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