#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#define rep(i,n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
string convert(string s) {
string o = "";
for (char c : s) {
if (c == 'A') o += 'a';
else if (c == 'G') o += 'b';
else if (c == 'C') o += 'c';
else o += 'd';
}
return o;
}
string read() {
string s;
cin >> s;
return convert(s);
}
vector<int> radixSort(int p, vector<int> all, string *src) {
vector<int> s[4] = {};
vector<int> ret;
for (int x : all) {
if (src[x].size() == p) ret.pb(x);
else s[src[x][p]-'a'].pb(x);
}
rep(k, 4) if (!s[k].empty()) {
vector<int> r = radixSort(p+1, s[k], src);
ret.insert(ret.end(), all(r));
}
return ret;
}
struct Trie {
int val;
Trie *ch[4];
Trie() : val(0) {
rep(k, 4) ch[k] = NULL;
}
int find(const char *s) {
if (*s == '\0') return val;
int k = *s-'a';
if (ch[k] == NULL) return 0;
return ch[k]->find(s+1);
}
void add(const char *s) {
if (*s == '\0') {
val++;
return;
}
val++;
int k = *s-'a';
if (ch[k] == NULL) ch[k] = new Trie();
ch[k]->add(s+1);
}
void destroy() {
rep(k, 4) if (ch[k]) {
ch[k]->destroy();
delete ch[k];
}
}
};
struct Bucket {
vector<string> str;
Trie *trie;
Bucket() {
trie = new Trie();
}
void add(string s) {
str.pb(s);
trie->add(s.c_str());
}
void destroy() {
str.clear();
trie->destroy();
delete trie;
}
};
int N, Q;
string S[100000];
string Qpre[100000], Qsuf[100000];
Bucket data[200000];
int ans[100000];
bool is_prefix_of(const string &S, const string &T) {
if (T.size() > S.size()) return false;
rep(i, T.size()) if (T[i] != S[i]) return false;
return true;
}
int main() {
cin >> N >> Q;
rep(i, N) S[i] = read();
rep(i, Q) Qpre[i] = read(), Qsuf[i] = read();
vector<int> Si; rep(i, N) Si.pb(i); Si = radixSort(0, Si, S);
vector<int> Qi; rep(i, Q) Qi.pb(i); Qi = radixSort(0, Qi, Qpre);
reverse(all(Qi));
//rep(i, N) cout << S[Si[i]] << "\n";
set<P> vs;
rep(i, N) {
string srev(S[i]);
reverse(all(srev));
data[i].add(srev);
vs.insert(P(i, i));
}
int V = N;
for (int q : Qi) {
string &T = Qpre[q];
int l = 0;
while (l < N && S[Si[l]]<T) l++;
//cout<<"["<<l<<",] T="<<T<<"\n";
if (l == N || !is_prefix_of(S[Si[l]], T)) continue;
auto it = vs.lower_bound(P(l, -1));
bool ok = false;
while (it != vs.end() && is_prefix_of(S[Si[it->_1]], T)) {
if (!ok) assert(it->_1 == l);
ok = true;
int t = it->_2;
//cout<<"merge("<<t<<")\n";
if (data[V].str.size() < data[t].str.size()) swap(data[V], data[t]);
for (string s : data[t].str) data[V].add(s);
data[t].destroy();
it = vs.erase(it);
}
assert(ok);
vs.insert(P(l, V));
reverse(all(Qsuf[q]));
//cout<<"ans["<<q<<"]="<<data[V].str.size()<<".find("<<Qsuf[q]<<")\n";
ans[q] = data[V].trie->find(Qsuf[q].c_str());
V++;
}
rep(i, Q) cout << ans[i] << "\n";
return 0;
}
Compilation message
selling_rna.cpp: In function 'std::vector<int> radixSort(int, std::vector<int>, std::__cxx11::string*)':
selling_rna.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (src[x].size() == p) ret.pb(x);
^
selling_rna.cpp: In function 'bool is_prefix_of(const string&, const string&)':
selling_rna.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for (int i=0; i<(n); i++)
^
selling_rna.cpp:100:3: note: in expansion of macro 'rep'
rep(i, T.size()) if (T[i] != S[i]) return false;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
27416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
706 ms |
130584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1500 ms |
38804 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
27416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
