// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'
constexpr ll inf = 1e18, N = 2e6 + 10, mod = 1e9 + 9, pr = 1000696969;
string s[N];
int cnt[N], ans[N], n, m;
vector<int> sp[N], sf[N];
vector<pair<int, int> > query[N];
map<int, pair<int, int> > mp;
map<int, int> nu;
bool cmp(int i, int j) {
int l = 0, r = min(Sz(s[i]), Sz(s[j])), mid;
while(l < r - 1) {
mid = (l + r) >> 1;
if(sp[i][mid] == sp[j][mid]) {
l = mid;
continue;
}
r = mid;
}
if(l == n) return i < j;
return s[i][l + 1] < s[j][l + 1];
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
cin >>n >>m;
for(int i = 1; i <= n; i++) cin >>s[i], s[i] = '#' + s[i];
ll val = 0;
for(int i = 1; i <= n; i++) {
sp[i].resize(Sz(s[i]) + 5);
val = 0;
for(int j = 1; j < Sz(s[i]); j++) {
val *= pr, val += (s[i][j] - 'A' + 1);
val %= mod;
sp[i][j] = val;
}
sf[i].resize(Sz(s[i]) + 5);
val = 0;
for(int j = Sz(s[i]) - 1; j > 0; j--) {
val *= pr, val += (s[i][j] - 'A' + 1);
val %= mod;
sf[i][j] = val;
}
}
vector<int> vc;
for(int i = 1; i <= n; i++) vc.push_back(i);
sort(All(vc), cmp);
string temp = "";
for(int i = 0; i < n; i++) {
temp += s[vc[i]];
}
int tim = 0;
val = 0;
for(auto c : temp) {
if(c == '#') {
val = 0;
tim++; continue;
}
val *= pr, val += (c - 'A' + 1);
val %= mod;
if(mp[val].first == 0) mp[val].first = tim;
mp[val].second = tim;
}
for(int i = 0; i < m; i++) {
string A, B; cin >>A >>B;
ll valA = 0, valB = 0;
for(int j = 0; j < Sz(A); j++) {
valA *= pr, valA += (A[j] - 'A' + 1);
valA %= mod;
}
for(int j = Sz(B) - 1; j >= 0; j--) {
valB *= pr, valB += (B[j] - 'A' + 1);
valB %= mod;
}
if(mp[valA].first == 0) {
ans[valA] = 0;
continue;
}
query[mp[valA].first].push_back({i, 0});
query[mp[valA].second].push_back({i, 1});
cnt[i] = valB;
}
for(int i = 0; i < n; i++) {
for(auto j : query[i + 1]) {
if(j.second == 1) continue;
ans[j.first] -= nu[cnt[j.first]];
}
for(int j = Sz(s[vc[i]]) - 1; j > 0; j--) {
nu[sf[vc[i]][j]]++;
}
for(auto j : query[i + 1]) {
if(j.second == 0) continue;
ans[j.first] += nu[cnt[j.first]];
}
}
for(int i = 0; i < m; i++) cout<<ans[i] <<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
203852 KB |
Output is correct |
| 2 |
Correct |
93 ms |
203808 KB |
Output is correct |
| 3 |
Correct |
90 ms |
203860 KB |
Output is correct |
| 4 |
Correct |
99 ms |
203820 KB |
Output is correct |
| 5 |
Correct |
98 ms |
203824 KB |
Output is correct |
| 6 |
Correct |
90 ms |
203844 KB |
Output is correct |
| 7 |
Correct |
92 ms |
203848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
290928 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
210992 KB |
Output is correct |
| 2 |
Correct |
128 ms |
208812 KB |
Output is correct |
| 3 |
Correct |
146 ms |
210140 KB |
Output is correct |
| 4 |
Correct |
119 ms |
208684 KB |
Output is correct |
| 5 |
Correct |
132 ms |
208940 KB |
Output is correct |
| 6 |
Correct |
153 ms |
210112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
203852 KB |
Output is correct |
| 2 |
Correct |
93 ms |
203808 KB |
Output is correct |
| 3 |
Correct |
90 ms |
203860 KB |
Output is correct |
| 4 |
Correct |
99 ms |
203820 KB |
Output is correct |
| 5 |
Correct |
98 ms |
203824 KB |
Output is correct |
| 6 |
Correct |
90 ms |
203844 KB |
Output is correct |
| 7 |
Correct |
92 ms |
203848 KB |
Output is correct |
| 8 |
Execution timed out |
1573 ms |
290928 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
