// 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, Log = 30;
string s[N], t;
int Rank[N][Log], p[N], cnt[N], ans[N], n, m, lg;
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];
}*/
bool cmp(int i, int j) {
if(Rank[i][lg - 1] != Rank[j][lg - 1]) return Rank[i][lg - 1] < Rank[j][lg - 1];
if(max(i, j) + (1 << (lg - 1)) > Sz(t)) return i < j;
return Rank[i + (1 << (lg - 1))][lg - 1] < Rank[j + (1 << (lg - 1))][lg - 1];
}
void build() {
t = "";
for(int i = 1; i <= n; i++) {
for(auto c : s[i]) t.push_back(c);
}
for(int i = 0; i < Sz(t); i++) p[i] = i, Rank[i][0] = t[i];
for(lg = 1; lg < Log; lg++) {
sort(p, p + Sz(t), cmp);
Rank[p[0]][lg] = 0;
for(int j = 1; j < Sz(t); j++) {
Rank[p[j]][lg] = Rank[p[j - 1]][lg] + cmp(p[j - 1], p[j]);
}
}
}
bool cmp2(pair<int, int> i, pair<int, int> j) {
return Rank[i.first][lg] < Rank[j.first][lg];
}
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;
}
}
build();
/*
vector<int> vc;
for(int i = 1; i <= n; i++) vc.push_back(i);
sort(All(vc), cmp);
*/
vector<int> vc;
vector<pair<int, int> > st;
int sum = 1;
for(int i = 1; i <= n; i++) {
st.push_back({sum, i});
sum += Sz(s[i]);
}
sort(All(st), cmp2);
for(auto i : st) vc.push_back(i.second);
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;
}
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 |
Incorrect |
91 ms |
203936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1437 ms |
942512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1012 ms |
229560 KB |
Output is correct |
| 2 |
Incorrect |
904 ms |
224964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
203936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
