#include <bits/stdc++.h>
#define ff first
#define ss second
const int MOD = 1e7 ;
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 marc[MOD+10] ;
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 ) ;
marc[cur_sum] = 1 ;
}
int Key = 1 ;
for(int i = 0 ; i < MOD ; i++ )
if(marc[i]) marc[i] = Key ++ ;
for(int i = 1 ; i <= m ; i++ )
{
my_hash[i-1] = marc[ 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 ++ ;
if( marc[cur_sum] == 0 ) continue ;
our_trie[ marc[cur_sum] ].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:109: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:113: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 |
39 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
40 ms |
16992 KB |
Output is correct |
| 3 |
Correct |
39 ms |
17016 KB |
Output is correct |
| 4 |
Correct |
40 ms |
16888 KB |
Output is correct |
| 5 |
Correct |
39 ms |
16888 KB |
Output is correct |
| 6 |
Correct |
39 ms |
16888 KB |
Output is correct |
| 7 |
Correct |
43 ms |
16888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
37176 KB |
Output is correct |
| 2 |
Correct |
261 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
455 ms |
31608 KB |
Output is correct |
| 4 |
Correct |
469 ms |
31608 KB |
Output is correct |
| 5 |
Incorrect |
256 ms |
77944 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
23668 KB |
Output is correct |
| 2 |
Correct |
80 ms |
20984 KB |
Output is correct |
| 3 |
Correct |
89 ms |
22340 KB |
Output is correct |
| 4 |
Correct |
82 ms |
21356 KB |
Output is correct |
| 5 |
Correct |
80 ms |
20984 KB |
Output is correct |
| 6 |
Correct |
87 ms |
22340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
16888 KB |
Output is correct |
| 2 |
Correct |
40 ms |
16992 KB |
Output is correct |
| 3 |
Correct |
39 ms |
17016 KB |
Output is correct |
| 4 |
Correct |
40 ms |
16888 KB |
Output is correct |
| 5 |
Correct |
39 ms |
16888 KB |
Output is correct |
| 6 |
Correct |
39 ms |
16888 KB |
Output is correct |
| 7 |
Correct |
43 ms |
16888 KB |
Output is correct |
| 8 |
Correct |
257 ms |
37176 KB |
Output is correct |
| 9 |
Correct |
261 ms |
31608 KB |
Output is correct |
| 10 |
Correct |
455 ms |
31608 KB |
Output is correct |
| 11 |
Correct |
469 ms |
31608 KB |
Output is correct |
| 12 |
Incorrect |
256 ms |
77944 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
