Submission #250575

#	Time	Username	Problem	Language	Result	Execution time	Memory
250575		CaroLinda	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1605 ms	267680 KiB

selling_rna

#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][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 (stderr)

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 ) ;
             ~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40