oj.uz

Submission #250575

# Submission time Handle Problem Language Result Execution time Memory
250575 2020-07-18T12:09:49 Z CaroLinda Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 267680 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 144376 KB Output is correct
2 Correct 124 ms 144500 KB Output is correct
3 Correct 121 ms 144376 KB Output is correct
4 Correct 120 ms 144376 KB Output is correct
5 Correct 121 ms 144376 KB Output is correct
6 Correct 129 ms 144492 KB Output is correct
7 Correct 122 ms 144376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 211832 KB Output is correct
2 Correct 647 ms 212600 KB Output is correct
3 Correct 665 ms 213648 KB Output is correct
4 Correct 629 ms 212868 KB Output is correct
5 Correct 650 ms 158872 KB Output is correct
6 Correct 649 ms 158920 KB Output is correct
7 Correct 527 ms 216056 KB Output is correct
8 Correct 694 ms 185608 KB Output is correct
9 Correct 676 ms 190712 KB Output is correct
10 Correct 498 ms 179076 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 200956 KB Output is correct
2 Correct 463 ms 177212 KB Output is correct
3 Correct 517 ms 188928 KB Output is correct
4 Correct 420 ms 180980 KB Output is correct
5 Correct 437 ms 177212 KB Output is correct
6 Correct 535 ms 188896 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 144376 KB Output is correct
2 Correct 124 ms 144500 KB Output is correct
3 Correct 121 ms 144376 KB Output is correct
4 Correct 120 ms 144376 KB Output is correct
5 Correct 121 ms 144376 KB Output is correct
6 Correct 129 ms 144492 KB Output is correct
7 Correct 122 ms 144376 KB Output is correct
8 Correct 610 ms 211832 KB Output is correct
9 Correct 647 ms 212600 KB Output is correct
10 Correct 665 ms 213648 KB Output is correct
11 Correct 629 ms 212868 KB Output is correct
12 Correct 650 ms 158872 KB Output is correct
13 Correct 649 ms 158920 KB Output is correct
14 Correct 527 ms 216056 KB Output is correct
15 Correct 694 ms 185608 KB Output is correct
16 Correct 676 ms 190712 KB Output is correct
17 Correct 498 ms 179076 KB Output is correct
18 Correct 557 ms 200956 KB Output is correct
19 Correct 463 ms 177212 KB Output is correct
20 Correct 517 ms 188928 KB Output is correct
21 Correct 420 ms 180980 KB Output is correct
22 Correct 437 ms 177212 KB Output is correct
23 Correct 535 ms 188896 KB Output is correct
24 Correct 821 ms 213072 KB Output is correct
25 Correct 935 ms 217548 KB Output is correct
26 Correct 690 ms 211832 KB Output is correct
27 Correct 742 ms 213424 KB Output is correct
28 Execution timed out 1605 ms 267680 KB Time limit exceeded
29 Halted 0 ms 0 KB -