#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define maxd 200010
#define pii pair<int, int>
#define insert trieadd
#define mp make_pair
//might need to double hash but whatever
const bool debug = false;
int N, M;
int BIT[maxn];
int ans[maxn]; //for printing b/c we do not compute in order
vector<pair< pair<string, string>, int>> cust; //customers
vector<vector<int>> activate(maxn); //indices of original guys
vector<vector<int>> deactivate(maxn);
vector<string> ostr;
int enc[27];
int endcust[maxn];
int endostr[maxn];
int trie[maxd][4]; //store indices
int tcind[maxd];
int numnodes = 1; //start at node 1
void insert(string cur, int ind) {
++ind;
int tmp = 1;
for (int i = 0; i < cur.length(); i++) {
int nx = enc[cur[i]-'A'];
if (trie[tmp][nx]) {
tmp = trie[tmp][nx];
continue;
}
trie[tmp][nx] = ++numnodes;
tmp = numnodes;
}
if (tcind[tmp] == 0) tcind[tmp] = ind;
}
vector<int> matches;
void qt(string cur) {
int tmp = 1;
for (int i = 0; i < cur.length(); i++) {
int nx = enc[cur[i]-'A'];
if (!trie[tmp][nx]) return;
tmp = trie[tmp][nx];
if (tcind[tmp]) matches.push_back(tcind[tmp]-1);
}
}
int qu(int spot) {
int ans = 0;
while (spot > 0) {
ans += BIT[spot];
spot -= spot & (-spot);
}
return ans;
}
int query(int lo, int hi) {
++hi;
++lo;
return qu(hi) - qu(lo-1);
}
void up(int ind, int diff) {
while (ind < maxn) {
BIT[ind] += diff;
ind += ind & (-ind);
}
}
void update(int ind, int diff) {
++ind;
up(ind, diff);
}
int main() {
enc['A'-'A'] = 0;
enc['C'-'A'] = 1;
enc['G'-'A'] = 2;
enc['U'-'A'] = 3;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
string cur;
for (int i = 0; i < N; i++) {
cin >> cur;
string rev = "" + cur;
reverse(rev.begin(), rev.end());
ostr.push_back(rev);
}
sort(ostr.begin(), ostr.end()); //should be fast enough
string pref, suf;
for (int i = 0; i < M; i++) {
cin >> pref >> suf;
cust.push_back(mp(mp(pref, suf), i));
}
sort(cust.begin(), cust.end()); //should be fast enough
if (debug) {
cout << endl;
cout << "asdfgfahafdsdvadfbashbasf OSTR" << endl;
for (int i = 0; i < ostr.size(); i++) {
cout << ostr[i] << endl;
}
cout << endl;
cout << endl;
for (int i = 0; i < cust.size(); i++) {
cout << cust[i].first.first << " " <<
cust[i].first.second <<
" " << cust[i].second << endl;
}
cout << endl;
}
vector<string> cp; //customer prefixes
for (int i = 0; i < M; i++) {
cp.push_back(cust[i].first.first);
}
endcust[cp.size()-1] = cp.size()-1;
for (int i = cp.size()-2; i >= 0; i--) {
if (cp[i] == cp[i+1]) {
endcust[i] = endcust[i+1];
}
else endcust[i] = i;
}
endostr[ostr.size()-1] = ostr.size()-1;
for (int i = ostr.size()-2; i >= 0; i--) {
if (ostr[i] == ostr[i+1]) {
endostr[i] = endostr[i+1];
}
else endostr[i] = i;
}
for (int i = 0; i < cp.size(); i++) {
insert(cp[i], i);
}
for (int i = 0; i < ostr.size(); i++) {
string rev = "" + ostr[i];
reverse(rev.begin(), rev.end());
matches.clear();
qt(rev); //find all the prefix matches for this
if (debug) cout << rev << " matches:" << endl;
for (int val : matches) {
activate[val].push_back(i);
deactivate[endcust[val]+1].push_back(i);
if (debug)
cout << " " << val << " " << endcust[val] << endl;
}
}
//clear out the trie b/c why not
numnodes = 1;
for (int i = 0; i < maxd; i++) {
trie[i][0] = trie[i][1] = trie[i][2] = trie[i][3] = 0;
tcind[i] = 0;
}
// for (int i = 0; i < ostr.size(); i++) {
// insert(ostr[i], i);
// }
if (debug) cout << endl << "----------------" << endl << endl;
//looping through the M strings
for (int i = 0; i < M; i++) {
// cout << "i: " << i << endl;
for (int val : activate[i]) {
// cout << " adding in " << val << endl;
update(val, 1);
}
for (int val : deactivate[i]) {
// cout << " taking out " << val << endl;
update(val, -1);
}
int indo = cust[i].second;
string suf = cust[i].first.second;
//don't care at all about the prefix
string rev = "" + suf;
reverse(rev.begin(), rev.end());
//then do my queries
// matches.clear();
// qt(rev);
//maybe i want binary serach for this half
int lo = 0;
int hi = ostr.size()-1;
int rl = rev.length();
while (lo < hi) {
int mid = (lo+hi)/2;
if (ostr[mid].length() < rl) {
if (rev < ostr[mid]) {
hi = mid;
}
else lo = mid+1;
continue;
}
if (rev > ostr[mid].substr(0, rl)) {
lo = mid+1;
}
else {
hi = mid;
}
}
int qs = lo;
if (ostr[qs].length() < rev.length() ||
ostr[qs].substr(0, rev.length()) != rev) {
if (debug) cout << rev << " DOES NOT MATCH" << endl;
continue; //no match
}
lo = 0;
hi = ostr.size()-1;
while (lo < hi) {
int mid = (lo+hi+1)/2;
if (ostr[mid].length() < rl) {
if (rev < ostr[mid]) {
hi = mid-1;
}
else lo = mid;
continue;
}
if (rev < ostr[mid].substr(0, rl)) {
hi = mid-1;
}
else {
lo = mid;
}
}
// cout << rev << " matches from " << lo << " to " << hi << endl;
int qe = lo;
if (debug) cout << rev << " matches from " << qs << " to " << qe << endl;
ans[indo] = query(qs, qe);
}
for (int i = 0; i < M; i++) {
cout << ans[i] << '\n';
}
cout.flush();
cin >> N;
}
//don't think we actually need a hash, we can just bin search
Compilation message
selling_rna.cpp: In function 'void trieadd(std::__cxx11::string, int)':
selling_rna.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cur.length(); i++) {
~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void qt(std::__cxx11::string)':
selling_rna.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cur.length(); i++) {
~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ostr.size(); i++) {
~~^~~~~~~~~~~~~
selling_rna.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cust.size(); i++) {
~~^~~~~~~~~~~~~
selling_rna.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cp.size(); i++) {
~~^~~~~~~~~~~
selling_rna.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ostr.size(); i++) {
~~^~~~~~~~~~~~~
selling_rna.cpp:204:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ostr[mid].length() < rl) {
~~~~~~~~~~~~~~~~~~~^~~~
selling_rna.cpp:230:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ostr[mid].length() < rl) {
~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9136 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9212 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9288 KB |
Output is correct |
| 7 |
Correct |
11 ms |
9304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
28060 KB |
Output is correct |
| 2 |
Correct |
283 ms |
36040 KB |
Output is correct |
| 3 |
Correct |
54 ms |
36040 KB |
Output is correct |
| 4 |
Correct |
53 ms |
36040 KB |
Output is correct |
| 5 |
Runtime error |
41 ms |
36040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
36040 KB |
Output is correct |
| 2 |
Correct |
74 ms |
36040 KB |
Output is correct |
| 3 |
Correct |
117 ms |
36040 KB |
Output is correct |
| 4 |
Correct |
83 ms |
36040 KB |
Output is correct |
| 5 |
Correct |
72 ms |
36040 KB |
Output is correct |
| 6 |
Correct |
96 ms |
36040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9136 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9212 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9288 KB |
Output is correct |
| 6 |
Correct |
9 ms |
9288 KB |
Output is correct |
| 7 |
Correct |
11 ms |
9304 KB |
Output is correct |
| 8 |
Correct |
168 ms |
28060 KB |
Output is correct |
| 9 |
Correct |
283 ms |
36040 KB |
Output is correct |
| 10 |
Correct |
54 ms |
36040 KB |
Output is correct |
| 11 |
Correct |
53 ms |
36040 KB |
Output is correct |
| 12 |
Runtime error |
41 ms |
36040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Halted |
0 ms |
0 KB |
- |
