oj.uz

Submission #57131

# Submission time Handle Problem Language Result Execution time Memory
57131 2018-07-14T06:14:56 Z 노영훈(#1652) Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 745 ms 501472 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9, TMX=2000010;

int f(char c){
    if(c=='A') return 0;
    if(c=='C') return 1;
    if(c=='G') return 2;
    if(c=='U') return 3;
    return -1;
}

struct node1 {
    int link[4];
    int l, r;
} p_trie[TMX];
int now_p=1;

int n, m;
string S[MX];


int init_pref(int v, int idx, int pos){
    if(v==0) v=++now_p;
    node1 &nd=p_trie[v];
    
    if(nd.l==0) nd.l=nd.r=idx;
    else nd.r=idx;

    if(pos==(int)S[idx].size()-1) return v;
    int to=f(S[idx][pos+1]);

    nd.link[to]=init_pref(nd.link[to], idx, pos+1);

    return v;
}

void dfs(int v){
    if(v==0){ cout<<"OUT\n"; return;}
    node1 &nd=p_trie[v];
    cout<<v<<' '<<nd.l<<' '<<nd.r<<'\n';
    for(int i=0; i<4; i++)
        cout<<"GO: "<<i<<'\n', dfs(nd.link[i]);
    cout<<"OUT\n";
}

struct node2 {
    int link[4];
    int cnt;
} s_trie[20*TMX];
int now_s;

int tree[4*MX];

int init_suff(int v, int idx, int pos){
    if(v==0) v=++now_s;
    node2 &nd=s_trie[v];
    
    nd.cnt++;

    if(pos==0) return v;
    int to=f(S[idx][pos-1]);

    nd.link[to]=init_suff(nd.link[to], idx, pos-1);

    return v;
}

void init_seg(int v, int s, int e){
    tree[v]=++now_s;
    for(int i=s; i<=e; i++)
        init_suff(tree[v], i, S[i].size());
    if(s==e) return;
    init_seg(v*2, s, (s+e)/2);
    init_seg(v*2+1, (s+e)/2+1, e);
}

pii find_p(int v, int pos, string &S){
    if(v==0) return pii(0,0);
    node1 &nd=p_trie[v];
    if(pos==(int)S.size()-1) return pii(nd.l, nd.r);
    int to=f(S[pos+1]);
    
    return find_p(nd.link[to], pos+1, S);
}

int find_s(int v, int pos, string &S){
    if(v==0) return 0;
    node2 &nd=s_trie[v];
    if(pos==(int)S.size()-1) return nd.cnt;
    int to=f(S[pos+1]);

    return find_s(nd.link[to], pos+1, S);
}

int count(int v, int s, int e, int l, int r, string &S){
    if(r<s || e<l) return 0;
    if(l<=s && e<=r){
        return find_s(tree[v], -1, S);
    }
    return count(v*2,s,(s+e)/2,l,r,S) + count(v*2+1,(s+e)/2+1,e,l,r,S);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>S[i];
    }
    sort(S+1, S+n+1);
    for(int i=1; i<=n; i++){
        init_pref(1, i, -1);
    }
    init_seg(1,1,n);

    for(int i=1; i<=m; i++){
        string P, Q; cin>>P>>Q; reverse(Q.begin(), Q.end());
        int l,r; tie(l,r)=find_p(1,-1,P);
        if(l==0) { cout<<0<<'\n'; continue; }
        cout<<count(1,1,n,l,r,Q)<<'\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3556 KB Output is correct
3 Correct 6 ms 3632 KB Output is correct
4 Correct 4 ms 3836 KB Output is correct
5 Correct 4 ms 3836 KB Output is correct
6 Correct 4 ms 3836 KB Output is correct
7 Correct 5 ms 3836 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 470684 KB Output is correct
2 Correct 675 ms 501472 KB Output is correct
3 Correct 541 ms 501472 KB Output is correct
4 Correct 460 ms 501472 KB Output is correct
5 Correct 541 ms 501472 KB Output is correct
6 Correct 584 ms 501472 KB Output is correct
7 Correct 242 ms 501472 KB Output is correct
8 Correct 569 ms 501472 KB Output is correct
9 Correct 441 ms 501472 KB Output is correct
10 Correct 464 ms 501472 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 501472 KB Output is correct
2 Correct 65 ms 501472 KB Output is correct
3 Correct 75 ms 501472 KB Output is correct
4 Correct 49 ms 501472 KB Output is correct
5 Correct 49 ms 501472 KB Output is correct
6 Correct 62 ms 501472 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3556 KB Output is correct
3 Correct 6 ms 3632 KB Output is correct
4 Correct 4 ms 3836 KB Output is correct
5 Correct 4 ms 3836 KB Output is correct
6 Correct 4 ms 3836 KB Output is correct
7 Correct 5 ms 3836 KB Output is correct
8 Correct 745 ms 470684 KB Output is correct
9 Correct 675 ms 501472 KB Output is correct
10 Correct 541 ms 501472 KB Output is correct
11 Correct 460 ms 501472 KB Output is correct
12 Correct 541 ms 501472 KB Output is correct
13 Correct 584 ms 501472 KB Output is correct
14 Correct 242 ms 501472 KB Output is correct
15 Correct 569 ms 501472 KB Output is correct
16 Correct 441 ms 501472 KB Output is correct
17 Correct 464 ms 501472 KB Output is correct
18 Correct 62 ms 501472 KB Output is correct
19 Correct 65 ms 501472 KB Output is correct
20 Correct 75 ms 501472 KB Output is correct
21 Correct 49 ms 501472 KB Output is correct
22 Correct 49 ms 501472 KB Output is correct
23 Correct 62 ms 501472 KB Output is correct
24 Correct 741 ms 501472 KB Output is correct
25 Correct 693 ms 501472 KB Output is correct
26 Correct 544 ms 501472 KB Output is correct
27 Correct 488 ms 501472 KB Output is correct
28 Correct 541 ms 501472 KB Output is correct
29 Correct 282 ms 501472 KB Output is correct