#include <bits/stdc++.h>
using namespace std;
int tr1[4][2000001];
int tr2[4][2000001];
vector<int> end1[2000001];
vector<int> end2[2000001];
int sum1[2000001];
int sum2[2000001];
int p1 = 1;
int p2 = 1;
int cpos = -1;
vector<int> cs;
int cind = -1;
class Query{
public:
int tim, x, id;
bool add;
Query(int a, int b, int d, bool c){
tim = a;
x = b;
id = d;
add = c;
}
bool operator<(const Query &o) const{
return tim<o.tim;
}
};
void add1(int now){
sum1[now]++;
if(cpos==cs.size()){
end1[now].push_back(cind);
return;
}
if(tr1[cs[cpos]][now]==-1){
tr1[cs[cpos]][now] = p1++;
}
cpos++;
add1(tr1[cs[cpos-1]][now]);
}
void add2(int now){
sum2[now]++;
if(cpos==cs.size()){
end2[now].push_back(cind);
return;
}
if(tr2[cs[cpos]][now]==-1){
tr2[cs[cpos]][now] = p2++;
}
cpos++;
add2(tr2[cs[cpos-1]][now]);
}
pair<int, int> r1(int now){
if(cpos==cs.size()){
return make_pair(0,sum1[now]);
}
if(tr1[cs[cpos]][now]==-1){
return make_pair(0,0);
}
int bef = end1[now].size();
for(int i = 0; i<cs[cpos]; i++){
if(tr1[i][now]!=-1){
bef += sum1[tr1[i][now]];
}
}
cpos++;
pair<int, int> ret = r1(tr1[cs[cpos-1]][now]);
ret.first += bef;
return ret;
}
pair<int, int> r2(int now){
if(cpos==cs.size()){
return make_pair(0,sum2[now]);
}
if(tr2[cs[cpos]][now]==-1){
return make_pair(0,0);
}
int bef = end2[now].size();
for(int i = 0; i<cs[cpos]; i++){
if(tr2[i][now]!=-1){
bef += sum2[tr2[i][now]];
}
}
cpos++;
pair<int, int> ret = r2(tr2[cs[cpos-1]][now]);
ret.first += bef;
return ret;
}
vector<int> l1;
vector<int> l2;
void s1(int now){
for(int i = 0; i<end1[now].size(); i++){
l1.push_back(end1[now][i]);
}
for(int i = 0; i<4; i++){
if(tr1[i][now]!=-1){
s1(tr1[i][now]);
}
}
}
void s2(int now){
for(int i = 0; i<end2[now].size(); i++){
l2.push_back(end2[now][i]);
}
for(int i = 0; i<4; i++){
if(tr2[i][now]!=-1){
s2(tr2[i][now]);
}
}
}
int ff(char c){
if(c=='A'){
return 0;
}
if(c=='C'){
return 1;
}
if(c=='G'){
return 2;
}
return 3;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
for(int i = 0; i<4; i++){
for(int j = 0; j<=2000000; j++){
tr1[i][j] = -1;
tr2[i][j] = -1;
sum1[j] = 0;
sum2[j] = 0;
}
}
int n, m;
cin >> n >> m;
vector<int> f[n];
vector<int> b[n];
for(int i = 0; i<n; i++){
string s;
cin >> s;
for(int j = 0; j<s.length(); j++){
f[i].push_back(ff(s[j]));
}
for(int j = s.length()-1; j>=0; j--){
b[i].push_back(ff(s[j]));
}
}
for(int i = 0; i<n; i++){
cs = f[i];
cpos = 0;
cind = i;
add1(0);
cpos = 0;
cs = b[i];
add2(0);
}
s1(0);
s2(0);
// for(int i = 0; i<n; i++){
// cout << l1[i] << endl;
// }
// for(int i = 0; i<n; i++){
// cout << l2[i] << endl;
// }
int fir[n];
int sec[n];
for(int i = 0; i<n; i++){
fir[l1[i]] = i+1;
sec[l2[i]] = i+1;
}
vector<pair<int, int> > li;
for(int i = 0; i<n; i++){
li.push_back(make_pair(fir[i],sec[i]));
}
sort(li.begin(),li.end());
int ans[m];
for(int i = 0; i<m; i++){
ans[i] = 0;
}
vector<Query> q;
//tim, x, id, add
for(int i = 0; i<m; i++){
string a, bb;
cin >> a >> bb;
vector<int> f;
vector<int> b;
for(int j = 0; j<a.length(); j++){
f.push_back(ff(a[j]));
}
for(int j = bb.length()-1; j>=0; j--){
b.push_back(ff(bb[j]));
}
cs = f;
cpos = 0;
pair<int, int> ra = r1(0);
cs = b;
cpos = 0;
pair<int, int> rb = r2(0);
q.push_back(Query(ra.first,rb.first,i,true));
q.push_back(Query(ra.first,rb.first+rb.second,i,false));
q.push_back(Query(ra.first+ra.second,rb.first,i,false));
q.push_back(Query(ra.first+ra.second,rb.first+rb.second,i,true));
}
sort(q.begin(),q.end());
for(int i = 0; i<q.size(); i++){
int now = 0;
for(int j = 0; j<n; j++){
if(fir[j]<=q[i].tim && sec[j]<=q[i].x){
now++;
}
}
if(q[i].add){
ans[q[i].id] += now;
}
else{
ans[q[i].id] -= now;
}
}
for(int i = 0; i<m; i++){
cout << ans[i] << endl;
}
}
Compilation message
selling_rna.cpp: In function 'void add1(int)':
selling_rna.cpp:31:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cpos==cs.size()){
~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void add2(int)':
selling_rna.cpp:43:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cpos==cs.size()){
~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> r1(int)':
selling_rna.cpp:54:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cpos==cs.size()){
~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> r2(int)':
selling_rna.cpp:72:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(cpos==cs.size()){
~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void s1(int)':
selling_rna.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<end1[now].size(); i++){
~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void s2(int)':
selling_rna.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<end2[now].size(); i++){
~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:141:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<s.length(); j++){
~^~~~~~~~~~~
selling_rna.cpp:187:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<a.length(); j++){
~^~~~~~~~~~~
selling_rna.cpp:205:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<q.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
172628 KB |
Output is correct |
| 2 |
Correct |
156 ms |
172636 KB |
Output is correct |
| 3 |
Correct |
157 ms |
172752 KB |
Output is correct |
| 4 |
Correct |
151 ms |
172752 KB |
Output is correct |
| 5 |
Correct |
164 ms |
172752 KB |
Output is correct |
| 6 |
Correct |
171 ms |
172832 KB |
Output is correct |
| 7 |
Correct |
155 ms |
172832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
386 ms |
196204 KB |
Output is correct |
| 2 |
Correct |
662 ms |
202604 KB |
Output is correct |
| 3 |
Correct |
473 ms |
205812 KB |
Output is correct |
| 4 |
Correct |
623 ms |
210428 KB |
Output is correct |
| 5 |
Correct |
663 ms |
210428 KB |
Output is correct |
| 6 |
Correct |
698 ms |
210428 KB |
Output is correct |
| 7 |
Correct |
335 ms |
214628 KB |
Output is correct |
| 8 |
Correct |
662 ms |
224264 KB |
Output is correct |
| 9 |
Correct |
603 ms |
230072 KB |
Output is correct |
| 10 |
Correct |
428 ms |
233508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1588 ms |
233508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
172628 KB |
Output is correct |
| 2 |
Correct |
156 ms |
172636 KB |
Output is correct |
| 3 |
Correct |
157 ms |
172752 KB |
Output is correct |
| 4 |
Correct |
151 ms |
172752 KB |
Output is correct |
| 5 |
Correct |
164 ms |
172752 KB |
Output is correct |
| 6 |
Correct |
171 ms |
172832 KB |
Output is correct |
| 7 |
Correct |
155 ms |
172832 KB |
Output is correct |
| 8 |
Correct |
386 ms |
196204 KB |
Output is correct |
| 9 |
Correct |
662 ms |
202604 KB |
Output is correct |
| 10 |
Correct |
473 ms |
205812 KB |
Output is correct |
| 11 |
Correct |
623 ms |
210428 KB |
Output is correct |
| 12 |
Correct |
663 ms |
210428 KB |
Output is correct |
| 13 |
Correct |
698 ms |
210428 KB |
Output is correct |
| 14 |
Correct |
335 ms |
214628 KB |
Output is correct |
| 15 |
Correct |
662 ms |
224264 KB |
Output is correct |
| 16 |
Correct |
603 ms |
230072 KB |
Output is correct |
| 17 |
Correct |
428 ms |
233508 KB |
Output is correct |
| 18 |
Execution timed out |
1588 ms |
233508 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
