#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 100001;
const ll INF = (1LL << 31);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const double eps = 0.0000000001;
vector <pii> events[100001];
int ce[NMAX];
class Trie{
public:
vector <int> preordine;
struct Node{
Node* v[4];
int first;
int second;
set <int> st;
Node(){
for(int i = 0; i < 4; i++){
v[i] = NULL;
}
}
};
Node* root;
void insert(Node* &node, string s, int ind, int nr){
if(node == NULL)
node = new Node();
if(ind == s.size()){
node->st.insert(nr);
return;
}
int c = s[ind] - '0';
insert(node->v[c], s, ind + 1, nr);
}
void DFS(Node* &node){
if(node == NULL)
return;
node->first = preordine.size();
for(auto x : node->st){
preordine.push_back(x);
}
for(int i = 0; i < 4; i++){
DFS(node->v[i]);
}
node->second = preordine.size() - 1;
}
pii interval(Node* &node, string s, int ind){
if(node == NULL){
return {-1, -1};
}
if(ind == s.size()){
return {node->first, node->second};
}
int c = s[ind] - '0';
return interval(node->v[c], s, ind + 1);
}
}pref, suf;
string transforma(string s){
for(int i = 0; i < s.size(); i++){
if(s[i] == 'A')
s[i] = '0';
if(s[i] == 'G')
s[i] = '1';
if(s[i] == 'C')
s[i] = '2';
if(s[i] == 'U')
s[i] = '3';
}
return s;
}
int n, m;
int sol[NMAX];
int aib[NMAX];
void update(int x){
for(int i = x; i <= n; i += i&(-i))
aib[i]++;
}
int query(int x){
int v = 0;
for(int i = x; i > 0; i -= i&(-i))
v += aib[i];
return v;
}
void Sweep(){
for(int i = 1; i <= n; i++){
update(ce[pref.preordine[i - 1]]);
for(auto x : events[i]){
int semn = 1;
if(x.second < 0)
semn = -1;
x.second = abs(x.second);
sol[x.second] += semn * query(x.first);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
s = transforma(s);
pref.insert(pref.root, s, 0, i);
reverse(s.begin(), s.end());
suf.insert(suf.root, s, 0, i);
}
pref.DFS(pref.root);
suf.DFS(suf.root);
for(int i = 0; i < suf.preordine.size(); i++){
ce[suf.preordine[i]] = i + 1;
}
for(int i = 1; i <= m; i++){
string a, b;
cin >> a >> b;
a = transforma(a);
b = transforma(b);
reverse(b.begin(), b.end());
pii timpa = pref.interval(pref.root, a, 0);
pii timpb = suf.interval(suf.root, b, 0);
int x1 = timpa.first + 1;
int x2 = timpa.second + 1;
int y1 = timpb.first + 1;
int y2 = timpb.second + 1;
if(x1 == 0 || y1 == 0){
sol[i] = 0;
continue;
}
events[x1 - 1].push_back({y1 - 1, i});
events[x1 - 1].push_back({y2, -i});
events[x2].push_back({y1 - 1, -i});
events[x2].push_back({y2, i});
}
Sweep();
for(int i = 1; i <= m; i++){
cout << sol[i] << "\n";
}
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void Trie::insert(Trie::Node*&, std::string, int, int)':
selling_rna.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if(ind == s.size()){
| ~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'pii Trie::interval(Trie::Node*&, std::string, int)':
selling_rna.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if(ind == s.size()){
| ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::string transforma(std::string)':
selling_rna.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < s.size(); i++){
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i = 0; i < suf.preordine.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1589 ms |
74868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
10416 KB |
Output is correct |
| 2 |
Correct |
40 ms |
8672 KB |
Output is correct |
| 3 |
Correct |
51 ms |
9828 KB |
Output is correct |
| 4 |
Correct |
47 ms |
8680 KB |
Output is correct |
| 5 |
Correct |
40 ms |
8428 KB |
Output is correct |
| 6 |
Correct |
50 ms |
9708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 8 |
Execution timed out |
1589 ms |
74868 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
