oj.uz

Submission #567819

# Submission time Handle Problem Language Result Execution time Memory
567819 2022-05-24T08:44:12 Z shahriarkhan Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1088 ms 644096 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 4e6 + 5 ;

vector<int> qc[MX] ;

int num[27] , ans[MX] ;

pair<int,int> Q[MX] ;

struct BIT
{
    int N = 0 ;
    vector<int> t ;
    void init(int n)
    {
        N = n ;
        t = vector<int> (n+2,0) ;
    }
    void update(int idx , int val)
    {
        for(int i = idx ; i <= N ; i += (i&(-i)))
        {
            t[i] += val ;
        }
    }
    int _query(int idx)
    {
        int ret = 0 ;
        for(int i = idx ; i >= 1 ; i -= (i&(-i)))
        {
            ret += t[i] ;
        }
        return ret ;
    }
    int query(int l , int r)
    {
        return _query(r)-_query(l-1) ;
    }
};

struct trie
{
    vector<int> vals[MX] ;
    int cur = 0 , nex[MX][5] , ed[MX] , tin[MX] , tout[MX] , timer = 0 ;
    BIT B ;
    void init()
    {
        for(int i = 0 ; i < MX ; ++i)
        {
            ed[i] = 0 , tin[i] = 0 , tout[i] = 0 ;
            for(int j = 0 ; j < 5 ; ++j)
            {
                nex[i][j] = 0 ;
            }
        }
        B.init(MX) ;
    }
    void add_string(int idx , string &s)
    {
        int siz = s.size() , v = 0 ;
        for(int i = 0 ; i < siz ; ++i)
        {
            int ts = num[s[i]-'A'] ;
            if(!nex[v][ts]) nex[v][ts] = ++cur ;
            v = nex[v][ts] , vals[v].push_back(idx) ;
        }
        ed[idx] = v ;
    }
    int find_string(string &p)
    {
        int siz = p.size() , v = 0 ;
        for(int i = 0 ; i < siz ; ++i)
        {
            int ts = num[p[i]-'A'] ;
            if(!nex[v][ts]) return -1 ;
            v = nex[v][ts] ;
        }
        return v ;
    }
    void traverse(int s)
    {
        tin[s] = ++timer ;
        for(int i = 0 ; i < 4 ; ++i)
        {
            if(!nex[s][i]) continue ;
            traverse(nex[s][i]) ;
        }
        tout[s] = ++timer ;
    }
    void add_num(int idx , int val)
    {
        B.update(tin[ed[idx]],val) ;
    }
    int query(int idx)
    {
        return B.query(tin[idx],tout[idx]) ;
    }
};

int main()
{
    num['A'-'A'] = 0 , num['G'-'A'] = 1 , num['C'-'A'] = 2 , num['U'-'A'] = 3 ;
    int n , m ;
    scanf("%d%d",&n,&m) ;
    trie pref , suf ;
    pref.init() , suf.init() ;
    for(int i = 1 ; i <= n ; ++i)
    {
        string s ;
        cin>>s ;
        pref.add_string(i,s) ;
        reverse(s.begin(),s.end()) ;
        suf.add_string(i,s) ;
    }
    suf.traverse(0) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        string p , q ;
        cin>>p>>q ;
        reverse(q.begin(),q.end()) ;
        int pr = pref.find_string(p) , sf = suf.find_string(q) ;
        if(pr<0) continue ;
        if(sf<0) continue ;
        qc[pr].push_back(i) ;
        Q[i] = {pr,sf} ;
    }
    for(int i = 0 ; i < MX ; ++i)
    {
        for(int j : pref.vals[i])
        {
            suf.add_num(j,1) ;
        }
        for(int j : qc[i])
        {
            ans[j] += suf.query(Q[j].second) ;
        }
        for(int j : pref.vals[i])
        {
            suf.add_num(j,-1) ;
        }
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        printf("%d\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 563840 KB Output is correct
2 Correct 483 ms 563836 KB Output is correct
3 Correct 351 ms 563816 KB Output is correct
4 Correct 342 ms 563900 KB Output is correct
5 Correct 329 ms 563940 KB Output is correct
6 Correct 308 ms 563840 KB Output is correct
7 Correct 357 ms 563808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 641040 KB Output is correct
2 Correct 1088 ms 637024 KB Output is correct
3 Correct 826 ms 639768 KB Output is correct
4 Correct 806 ms 636344 KB Output is correct
5 Correct 670 ms 643032 KB Output is correct
6 Correct 648 ms 644096 KB Output is correct
7 Correct 717 ms 586356 KB Output is correct
8 Correct 899 ms 626500 KB Output is correct
9 Correct 888 ms 618024 KB Output is correct
10 Correct 736 ms 615168 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 566532 KB Output is correct
2 Correct 359 ms 566084 KB Output is correct
3 Correct 333 ms 566336 KB Output is correct
4 Correct 375 ms 566004 KB Output is correct
5 Correct 335 ms 566088 KB Output is correct
6 Correct 349 ms 566212 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 563840 KB Output is correct
2 Correct 483 ms 563836 KB Output is correct
3 Correct 351 ms 563816 KB Output is correct
4 Correct 342 ms 563900 KB Output is correct
5 Correct 329 ms 563940 KB Output is correct
6 Correct 308 ms 563840 KB Output is correct
7 Correct 357 ms 563808 KB Output is correct
8 Correct 976 ms 641040 KB Output is correct
9 Correct 1088 ms 637024 KB Output is correct
10 Correct 826 ms 639768 KB Output is correct
11 Correct 806 ms 636344 KB Output is correct
12 Correct 670 ms 643032 KB Output is correct
13 Correct 648 ms 644096 KB Output is correct
14 Correct 717 ms 586356 KB Output is correct
15 Correct 899 ms 626500 KB Output is correct
16 Correct 888 ms 618024 KB Output is correct
17 Correct 736 ms 615168 KB Output is correct
18 Correct 345 ms 566532 KB Output is correct
19 Correct 359 ms 566084 KB Output is correct
20 Correct 333 ms 566336 KB Output is correct
21 Correct 375 ms 566004 KB Output is correct
22 Correct 335 ms 566088 KB Output is correct
23 Correct 349 ms 566212 KB Output is correct
24 Correct 943 ms 628740 KB Output is correct
25 Correct 974 ms 629548 KB Output is correct
26 Correct 959 ms 627916 KB Output is correct
27 Correct 730 ms 628044 KB Output is correct
28 Correct 783 ms 594172 KB Output is correct
29 Correct 598 ms 578720 KB Output is correct