#include <bits/stdc++.h>
#define ff first
#define ss second
const int MOD = 1e9+7 ;
const int MAX = 1e5+10 ;
const int SMAX = 2e6+10 ;
const int base = 31 ;
using namespace std ;
int resp[MAX] ;
int get_val(char c)
{
if( c == 'A' ) return 1 ;
if( c == 'C' ) return 2 ;
if( c == 'G' ) return 3 ;
return 4 ;
}
struct Trie
{
struct Node
{
int v[5] , soma ;
vector<int> end_here ;
Node() { for(int i = 0 ; i < 5 ; i++ ) v[i] = soma =0 ; }
} ;
int ptr ;
vector<Node> adj ;
Trie() { adj.push_back( Node() ) ; }
void add( vector<char> v, int idx, int para_somar )
{
int curr = 0 ;
for(int i = 0 ; i < (int)(v.size()) ; i++ )
{
int val = get_val( v[i] ) ;
adj[curr].soma += para_somar ;
if( adj[curr].v[val] == 0 )
{
if( para_somar == 1 ) return ;
adj.push_back( Node() ) ;
adj[curr].v[val] = ++ptr ;
}
curr = adj[curr].v[val] ;
}
if( para_somar == 0 )
adj[curr].end_here.push_back(idx) ;
adj[curr].soma += para_somar;
}
void anda()
{
queue<int> fila ;
fila.push(0) ;
while(!fila.empty())
{
int curr = fila.front() ;
fila.pop() ;
for(int i : adj[curr].end_here )
resp[i] = adj[curr].soma ;
for(int i = 0 ; i < 5 ; i ++ )
if( adj[curr].v[i] > 0 )
fila.push( adj[curr].v[i] ) ;
}
}
} ;
int n , m ;
vector<int> dif_tams ;
bool marc_tams[SMAX] ;
char str[MAX] ;
vector<char> to_sell[MAX] , to_buy_pref[MAX] , to_buy_suf[MAX] ;
vector< pair< long long int , int > > aux ;
long long pot[SMAX] ;
vector<long long> my_hash ;
unordered_map<long long , int> mp ;
Trie our_trie[MAX] ;
string s ;
int main()
{
//Reading input
scanf("%d%d", &n , &m) ;
for(int i = 1 ; i <= n ; i++ )
{
scanf("%s", str ) ;
int _n = strlen(str) ;
for(int j = 0 ; j < _n ; j++ ) to_sell[i].push_back( str[j] ) ;
}
getchar() ;
for(int i = 1 ; i <= m ; i++ )
{
getline( cin , s ) ;
int _n = s.size() , j = 0;
for(; s[j] != ' ' ; j++ )
to_buy_pref[i].push_back( s[j] ) ;
j ++ ;
for(; j < _n ; j++ ) to_buy_suf[i].push_back( s[j] ) ;
}
//
mp.reserve(m) ;
for(int i = 1 ; i <= m ; i++ )
{
marc_tams[ to_buy_suf[i].size() ] = true ;
long long cur_sum = 0LL ;
for(int j = to_buy_suf[i].size() - 1, idx = 0 ; j >= 0 ; j-- , idx++ )
{
cur_sum = ( cur_sum * base ) % MOD ;
cur_sum = ( cur_sum + get_val( to_buy_suf[i][j] ) ) % MOD ;
}
my_hash.push_back( cur_sum ) ;
mp.insert( make_pair(cur_sum,0) ) ;
}
int Key = 1 ;
for(auto &p : mp ) p.ss = Key ++ ;
for(int i = 1 ; i <= m ; i++ )
{
my_hash[i-1] = mp[ my_hash[i-1] ] ;
our_trie[ my_hash[i-1] ].add( to_buy_pref[i] , i , 0 ) ;
}
for(int i = 1 ; i <= SMAX ; i++ )
if( marc_tams[i] ) dif_tams.push_back(i) ;
// for(auto &p : mp ) printf("%lld %d\n" , p.ff, p.ss ) ;
for(int i = 1 ; i <= n ; i++ )
{
long long cur_sum = 0LL ;
for(int j = to_sell[i].size() - 1 , tot = 1 , idx = 0 ; j >= 0 ; j -- , tot++ )
{
cur_sum = ( cur_sum * base ) % MOD ;
cur_sum = ( cur_sum + get_val( to_sell[i][j] ) ) % MOD ;
if( tot == dif_tams[idx] )
{
idx ++ ;
unordered_map<long long, int>::iterator it = mp.find(cur_sum) ;
if( it == mp.end() ) continue ;
our_trie[ it->ss ].add( to_sell[i] , -1 , 1 ) ;
}
}
}
for(int i = 1 ; i < Key ; i++ ) our_trie[i].anda() ;
for(int i = 1 ; i <= m ; i++ ) printf("%d\n" , resp[i] ) ;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:108:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n , &m) ;
~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:112:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str ) ;
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
16760 KB |
Output is correct |
| 2 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 3 |
Correct |
28 ms |
16888 KB |
Output is correct |
| 4 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 5 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 6 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 7 |
Correct |
27 ms |
16760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
33080 KB |
Output is correct |
| 2 |
Correct |
239 ms |
27640 KB |
Output is correct |
| 3 |
Correct |
437 ms |
23596 KB |
Output is correct |
| 4 |
Correct |
460 ms |
23532 KB |
Output is correct |
| 5 |
Correct |
251 ms |
60408 KB |
Output is correct |
| 6 |
Correct |
251 ms |
60024 KB |
Output is correct |
| 7 |
Execution timed out |
1544 ms |
80632 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
23156 KB |
Output is correct |
| 2 |
Correct |
71 ms |
20600 KB |
Output is correct |
| 3 |
Correct |
82 ms |
21856 KB |
Output is correct |
| 4 |
Correct |
71 ms |
20976 KB |
Output is correct |
| 5 |
Correct |
69 ms |
20588 KB |
Output is correct |
| 6 |
Correct |
76 ms |
21876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
16760 KB |
Output is correct |
| 2 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 3 |
Correct |
28 ms |
16888 KB |
Output is correct |
| 4 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 5 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 6 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 7 |
Correct |
27 ms |
16760 KB |
Output is correct |
| 8 |
Correct |
247 ms |
33080 KB |
Output is correct |
| 9 |
Correct |
239 ms |
27640 KB |
Output is correct |
| 10 |
Correct |
437 ms |
23596 KB |
Output is correct |
| 11 |
Correct |
460 ms |
23532 KB |
Output is correct |
| 12 |
Correct |
251 ms |
60408 KB |
Output is correct |
| 13 |
Correct |
251 ms |
60024 KB |
Output is correct |
| 14 |
Execution timed out |
1544 ms |
80632 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
