This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 100000;
int x[N+5];
int y[N+5];
const int MAXC = 600000;
int gde[MAXC+5][26];
int tjm;
vector <pair <int, int>> graf[MAXC+5];
vector <int> koji[MAXC+5];
vector <int> queries[MAXC+5];
void trie_add(int t, int ind, const string &s){
int v = 0;
for(int i=0; i<s.size(); i++){
int x = s[i] - 'A';
if(!gde[v][x]){
gde[v][x] = ++tjm;
graf[v].push_back({tjm, x});
}
v = gde[v][x];
}
if(t == 1) koji[v].push_back(ind);
else queries[v].push_back(ind);
}
int xl[N+5], yl[N+5], xr[N+5], yr[N+5];
void dfs(int t, int v){
int in = ++tjm;
for(auto c : koji[v]){
if(t == 1) x[c] = in;
else y[c] = in;
}
for(auto c : graf[v]) dfs(t, c.first);
int out = ++tjm;
for(auto c : queries[v]){
if(t == 1){
xl[c] = in, xr[c] = out;
}
else{
yl[c] = in, yr[c] = out;
}
}
queries[v].clear();
koji[v].clear();
for(auto c : graf[v]){
gde[v][c.second] = 0;
}
graf[v].clear();
}
string s[N+5];
string qpref[N+5];
string qsuf[N+5];
int bit[MAXC+5];
void bit_add(int x){
while(x <= MAXC){
bit[x]++;
x += x & -x;
}
}
int bit_get(int x){
int res = 0;
while(x){
res += bit[x];
x -= x & -x;
}
return res;
}
const int INF = 1000000000;
vector <int> upds[MAXC+5];
vector <pair <pair <int, int>, int>> quers[MAXC+5];
int res[N+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int i=1; i<=n; i++){
cin >> s[i];
trie_add(1, i, s[i]);
}
for(int i=1; i<=m; i++){
cin >> qpref[i] >> qsuf[i];
trie_add(2, i, qpref[i]);
}
dfs(1, 0);
for(int i=1; i<=n; i++){
reverse(s[i].begin(), s[i].end());
trie_add(1, i, s[i]);
}
for(int i=1; i<=m; i++){
reverse(qsuf[i].begin(), qsuf[i].end());
trie_add(2, i, qsuf[i]);
}
tjm = 0;
dfs(2, 0);
for(int i=1; i<=n; i++){
upds[y[i]].push_back(x[i]);
}
for(int i=1; i<=m; i++){
quers[yr[i]].push_back({{xl[i], xr[i]}, i});
quers[yl[i] - 1].push_back({{xl[i], xr[i]}, -i});
}
for(int i=1; i<=MAXC; i++){
for(auto c : upds[i]) bit_add(c);
for(auto c : quers[i]){
int ind = c.second;
int kf = 1;
if(ind < 0){
ind = -ind;
kf = -1;
}
res[ind] += kf*(bit_get(c.first.second) - bit_get(c.first.first - 1));
}
}
for(int i=1; i<=m; i++) cout << res[i] << "\n";
return 0;
}
Compilation message (stderr)
selling_rna.cpp: In function 'void trie_add(int, int, const string&)':
selling_rna.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0; i<s.size(); i++){
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |