#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int MAXA = 110;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmx(int &a, int b){ a = max(a, b); }
int n, k, ans[MAXN];
string p[MAXN], q[MAXN];
vector <pair<string,int>> vec;
string te;
struct seg {
int cnt, idx;
seg* a[4];
void bd(int nw){
if(a[nw] == NULL){
a[nw] = new seg(); a[nw]->idx = idx+1; a[nw]->cnt = 0;
}
}
void upd(){
// if(idx!=-1) cout << te[idx] << ' '<< te << " te\n";
cnt++;
// cout << idx << ' ' << te <<"pp\n";
if(idx+1==te.size()) return;
if(te[idx+1] == 'A'){
bd(0); a[0]->upd();
} else if(te[idx+1] == 'C'){
bd(1); a[1]->upd();
} else if(te[idx+1] == 'U'){
bd(2); a[2]->upd();
} else if(te[idx+1] == 'G'){
bd(3); a[3]->upd();
}
}
int que(){
if(idx+1==te.size()) return cnt;
if(te[idx+1] == 'A'){
bd(0); return a[0]->que();
} else if(te[idx+1] == 'C'){
bd(1); return a[1]->que();
} else if(te[idx+1] == 'U'){
bd(2); return a[2]->que();
} else if(te[idx+1] == 'G'){
bd(3); return a[3]->que();
}
assert(false);
}
} *A;
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
A = new seg(); A->idx = -1;
cin >> n >> k;
for(int i=1; i<=n; i++){
string s; cin >> s; vec.pb({s, 0});
}
for(int i=1; i<=k; i++){
cin >> p[i] >> q[i];
for(int j=0; j<q[i].size()/2; i++) swap(q[i][j], q[i][q[i].size()-j-1]);
vec.pb({p[i], -i});
string te = p[i]; te += 'Z';
vec.pb({te, i});
}
sort(vec.begin(), vec.end());
// for(auto in : vec) cout << in.fi << ' ' << in.se << " vec\n";
for(auto in : vec){
if(in.se==0){
te = in.fi;
for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
// cout << te << " te\n";
A->upd();
// cout << A->a[1]->cnt << " cnt\n";
} else if(in.se < 0){
int id = -in.se, idx = 0;
te = q[id];
int ret = A->que();
ans[id] -= ret;
// cout << ret << ' ' << id << "id min\n";
} else {
int id = in.se, idx = 0;
te = q[id];
int ret = A->que();
ans[id] += ret;
// cout << ret << ' ' << id << "id plus\n";
}
}
for(int i=1; i<=k; i++) cout << ans[i] << '\n';
}
Compilation message
selling_rna.cpp: In member function 'void seg::upd()':
selling_rna.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | if(idx+1==te.size()) return;
| ~~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'long long int seg::que()':
selling_rna.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(idx+1==te.size()) return cnt;
| ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int j=0; j<q[i].size()/2; i++) swap(q[i][j], q[i][q[i].size()-j-1]);
| ~^~~~~~~~~~~~~~
selling_rna.cpp:91:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
| ~^~~~~~~~~~~~
selling_rna.cpp:96:30: warning: unused variable 'idx' [-Wunused-variable]
96 | int id = -in.se, idx = 0;
| ^~~
selling_rna.cpp:103:29: warning: unused variable 'idx' [-Wunused-variable]
103 | int id = in.se, idx = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
138416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
