#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
const int MAX = 4e5+10 ;
using namespace __gnu_pbds;
using namespace std ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
struct Seg
{
ordered_set t[MAX*4] ;
int m(int l, int r) { return (l+r)>>1 ; }
void upd(int pos, int l, int r, int idx, int val )
{
t[pos].insert(val) ;
if(l == r) return ;
if(idx <= m(l,r)) upd(pos<<1 ,l, m(l,r) , idx, val ) ;
else upd(pos<<1|1,m(l,r)+1, r, idx, val) ;
}
int qry(int pos, int l, int r , int beg, int en, int val1, int val2)
{
if( l > en || r < beg ) return 0 ;
if( l >= beg && r <= en ) return t[pos].order_of_key(val2) - t[pos].order_of_key(val1);
int al = qry(pos<<1 , l, m(l,r) , beg, en , val1, val2 ) ;
int ar = qry(pos<<1|1 , m(l,r) + 1 , r , beg, en ,val1, val2 ) ;
return al + ar ;
}
} seg ;
int N , M , T, curr ;
int id[MAX][2] ;
int tam[MAX][2] ;
char aux[MAX] ;
vector<char> str[MAX][2] ;
int get(char c)
{
if(c == 'A') return 0 ;
if( c == 'C' ) return 1 ;
if( c == 'G' ) return 2 ;
if(c == 'U') return 3 ;
return 4 ;
}
inline void process(int idx, int bit, vector<int> v )
{
vector<int> vv[5] ;
sort( all(v) , [&](int i, int j){return i > j ;} ) ;
for(auto e : v )
{
if( bit > tam[e][idx]-1 )
id[e][idx] = ++curr ;
else vv[ get(str[e][idx][bit]) ].pb(e) ;
}
for(int i = 0 ; i < 5 ; i++ )
if(vv[i].size() > 0)
process(idx, bit+1, vv[i]) ;
}
int main()
{
//Input ----------------------------------------
scanf("%d%d", &N , &M ) ; T = N+M ;
lp(i,1,N+1)
{
scanf("%s", aux) ;
tam[i][0] = tam[i][1] = strlen(aux) ;
lp(j,0,tam[i][0]) str[i][0].pb(aux[j]) ;
for(int j = tam[i][0]-1 ; j >= 0 ; j-- ) str[i][1].pb( aux[j] ) ;
}
lp(i,N+1,T+1)
lp(j,0,2)
{
scanf("%s", aux ) ;
tam[i][j] = strlen(aux) ;
lp(g,0,tam[i][j]) str[i][j].pb( aux[g] ) ;
}
lp(i,N+1,T+1)
{
str[i+T][0] = str[i][0] ;
str[i+T][0].pb('Z') ;
tam[i+T][0] = tam[i][0] + 1 ;
reverse( all(str[i][1]) ) ;
str[i+T][1] = str[i+T][1] ;
str[i+T][1].pb( 'Z' ) ;
tam[i+T][1] = tam[i][1] + 1 ;
}
//----------------------------------------------
vector<int> v(T) ;
iota(all(v),1) ;
lp(i,N+1,T+1) v.pb(i+T) ;
lp(i,0,2)
{
curr =0 ;
process(i,0,v) ;
}
lp(i,1,N+1) seg.upd(1,1,2*T,id[i][0], id[i][1]) ;
lp(i,N+1,T+1) printf("%d\n", seg.qry(1,1,2*T, id[i][0] , id[i+T][0] , id[i][1] , id[i+T][1] ) ) ;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N , &M ) ; T = N+M ;
~~~~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", aux) ;
~~~~~^~~~~~~~~~~
selling_rna.cpp:102:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", aux ) ;
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
144456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
614 ms |
215672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
576 ms |
200904 KB |
Output is correct |
| 2 |
Incorrect |
418 ms |
177260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
144456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
