//
// ROIGold.cpp
// Main calisma
//
// Created by Rakhman on 05/02/2019.
// Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)
const int MXN = 2e6 + 200;
const long long MNN = 1e5 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
//void istxt(bool yes){
// if(yes == 1){
// freopen("yinyang.in", "r", stdin);
// freopen("yinyang.out", "w", stdout);
// }else{
// freopen("/Users/rakhmanabdirashov/Desktop/input.txt", "r", stdin);
// }
//}
int n, sz = 0, rsz = 0, m, L, R, ans;
string s[MNN];
struct bor{
int nx[4];
int l, r;
vector<int> v;
}t[MXN];
int trans(char ch){
if(ch == 'A'){
return 0;
}else if(ch == 'U'){
return 1;
}else if(ch == 'G'){
return 2;
}else{
return 3;
}
}
void insert1(string s, int pos){
int cur = 0;
for(int i = 0; i < s.size(); i++){
int letter = trans(s[i]);
if(t[cur].nx[letter] == 0){
t[cur].nx[letter] = ++sz;
cur = sz;
t[cur].l = t[cur].r = pos;
}else{
cur = t[cur].nx[letter];
t[cur].r = pos;
}
}
}
void insert2(string s, int pos){
int cur = 0;
for(int i = 0; i < s.size(); i++){
int letter = trans(s[i]);
if(t[cur].nx[letter] == 0){
t[cur].nx[letter] = ++sz;
cur = sz;
t[cur].v.push_back(pos);
}else{
cur = t[cur].nx[letter];
t[cur].v.push_back(pos);
}
}
}
void get1(string s){
int cur = 0;
for(int i = 0; i < s.size(); i++){
cur = t[cur].nx[trans(s[i])];
}
L = t[cur].l, R = t[cur].r;
}
int get2(string s){
int cur = 0;
for(int i = 0; i < s.size(); i++){
cur = t[cur].nx[trans(s[i])];
}
int l = lower_bound(t[cur].v.begin(), t[cur].v.end(), L) - t[cur].v.begin();
int r = upper_bound(t[cur].v.begin(), t[cur].v.end(), R) - t[cur].v.begin();
return max(r - l, 0);
}
int main () {
ios;
//istxt(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i++){
insert1(s[i], i);
reverse(s[i].begin(), s[i].end());
insert2(s[i], i);
}
for(int i = 1; i <= m; i++){
string p, s;
cin >> p >> s;
get1(p);
cout << get2(s) << nl;
}
return 0;
}
Compilation message
selling_rna.cpp: In function 'void insert1(std::__cxx11::string, int)':
selling_rna.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
selling_rna.cpp: In function 'void insert2(std::__cxx11::string, int)':
selling_rna.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
selling_rna.cpp: In function 'void get1(std::__cxx11::string)':
selling_rna.cpp:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
selling_rna.cpp: In function 'int get2(std::__cxx11::string)':
selling_rna.cpp:123:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); i++){
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
872 ms |
97544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1593 ms |
146172 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
112 ms |
98676 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
872 ms |
97544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |