// 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);
/*
for(int i = 0; i < n; i++) {
ll val = 0;
for(int j = 1; j < Sz(s[vc[i]]); j++) {
val *= pr, val += (s[vc[i]][j] - 'A'+ 1);
val %= mod;
if(mp[val].first == 0) mp[val].first = i + 1;
mp[val].second = i + 1;
}
}
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;
}
// wtf(i), wtf(valA), wtf(valB), wtf(mp[valA].first), wtf(mp[valA].second);
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]];
// cout<<"&&&&" <<j.first <<" " <<ans[j.first] <<endl;
}
for(int j = Sz(s[vc[i]]) - 1; j > 0; j--) {
nu[sf[vc[i]][j]]++;
// cout<<"^&" <<i <<" " <<sf[vc[i]][j] <<endl;
}
for(auto j : query[i + 1]) {
if(j.second == 0) continue;
ans[j.first] += nu[cnt[j.first]];
// cout<<"&&&&" <<j.first <<" " <<ans[j.first] <<endl;
}
}
*/
for(int i = 0; i < m; i++) cout<<ans[i] <<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
203760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
221680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
137 ms |
209144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
203760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
