#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 Fenwick{
public:
vector<int> ar;
int n;
Fenwick(int a){
n = a+2;
ar.resize(n);
}
void add(int ind, int v){
for(;ind<n; ind += (ind&(-ind))){
ar[ind] += v;
}
}
int sum(int ind){
if(ind==0){
return 0;
}
int ret = 0;
for(;ind>0; ind -= (ind&(-ind))){
ret += ar[ind];
}
return ret;
}
};
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[n+1];
//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[ra.first].push_back(Query(ra.first,rb.first,i,true));
q[ra.first].push_back(Query(ra.first,rb.first+rb.second,i,false));
q[ra.first+ra.second].push_back(Query(ra.first+ra.second,rb.first,i,false));
q[ra.first+ra.second].push_back(Query(ra.first+ra.second,rb.first+rb.second,i,true));
}
Fenwick fen = Fenwick(n+2);
for(int i = 0; i<=n; i++){
for(int j = 0; j<q[i].size(); j++){
int now = fen.sum(q[i][j].x);
if(q[i][j].add){
ans[q[i][j].id] += now;
}
else{
ans[q[i][j].id] -= now;
}
}
if(i<n){
fen.add(li[i].second,1);
}
}
for(int i = 0; i<m; i++){
cout << ans[i] << endl;
}
}
Compilation message
selling_rna.cpp: In function 'void add1(int)':
selling_rna.cpp:55: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:67: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:78: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:96: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:116: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:126: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:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<s.length(); j++){
~^~~~~~~~~~~
selling_rna.cpp:211:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<a.length(); j++){
~^~~~~~~~~~~
selling_rna.cpp:230:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<q[i].size(); j++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
172664 KB |
Output is correct |
| 2 |
Correct |
175 ms |
172788 KB |
Output is correct |
| 3 |
Correct |
185 ms |
172788 KB |
Output is correct |
| 4 |
Correct |
168 ms |
172788 KB |
Output is correct |
| 5 |
Correct |
196 ms |
172808 KB |
Output is correct |
| 6 |
Correct |
167 ms |
172812 KB |
Output is correct |
| 7 |
Correct |
172 ms |
172812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
372 ms |
194328 KB |
Output is correct |
| 2 |
Correct |
368 ms |
196972 KB |
Output is correct |
| 3 |
Correct |
367 ms |
196972 KB |
Output is correct |
| 4 |
Correct |
362 ms |
196972 KB |
Output is correct |
| 5 |
Correct |
439 ms |
196972 KB |
Output is correct |
| 6 |
Correct |
423 ms |
196972 KB |
Output is correct |
| 7 |
Correct |
316 ms |
196972 KB |
Output is correct |
| 8 |
Correct |
400 ms |
196972 KB |
Output is correct |
| 9 |
Correct |
392 ms |
196972 KB |
Output is correct |
| 10 |
Correct |
332 ms |
196972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
196972 KB |
Output is correct |
| 2 |
Correct |
263 ms |
196972 KB |
Output is correct |
| 3 |
Correct |
300 ms |
196972 KB |
Output is correct |
| 4 |
Correct |
258 ms |
196972 KB |
Output is correct |
| 5 |
Correct |
295 ms |
196972 KB |
Output is correct |
| 6 |
Correct |
293 ms |
196972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
172664 KB |
Output is correct |
| 2 |
Correct |
175 ms |
172788 KB |
Output is correct |
| 3 |
Correct |
185 ms |
172788 KB |
Output is correct |
| 4 |
Correct |
168 ms |
172788 KB |
Output is correct |
| 5 |
Correct |
196 ms |
172808 KB |
Output is correct |
| 6 |
Correct |
167 ms |
172812 KB |
Output is correct |
| 7 |
Correct |
172 ms |
172812 KB |
Output is correct |
| 8 |
Correct |
372 ms |
194328 KB |
Output is correct |
| 9 |
Correct |
368 ms |
196972 KB |
Output is correct |
| 10 |
Correct |
367 ms |
196972 KB |
Output is correct |
| 11 |
Correct |
362 ms |
196972 KB |
Output is correct |
| 12 |
Correct |
439 ms |
196972 KB |
Output is correct |
| 13 |
Correct |
423 ms |
196972 KB |
Output is correct |
| 14 |
Correct |
316 ms |
196972 KB |
Output is correct |
| 15 |
Correct |
400 ms |
196972 KB |
Output is correct |
| 16 |
Correct |
392 ms |
196972 KB |
Output is correct |
| 17 |
Correct |
332 ms |
196972 KB |
Output is correct |
| 18 |
Correct |
364 ms |
196972 KB |
Output is correct |
| 19 |
Correct |
263 ms |
196972 KB |
Output is correct |
| 20 |
Correct |
300 ms |
196972 KB |
Output is correct |
| 21 |
Correct |
258 ms |
196972 KB |
Output is correct |
| 22 |
Correct |
295 ms |
196972 KB |
Output is correct |
| 23 |
Correct |
293 ms |
196972 KB |
Output is correct |
| 24 |
Correct |
402 ms |
205492 KB |
Output is correct |
| 25 |
Correct |
469 ms |
212548 KB |
Output is correct |
| 26 |
Correct |
426 ms |
212548 KB |
Output is correct |
| 27 |
Correct |
401 ms |
216908 KB |
Output is correct |
| 28 |
Correct |
680 ms |
242616 KB |
Output is correct |
| 29 |
Correct |
544 ms |
242616 KB |
Output is correct |
