oj.uz

Submission #962636

# Submission time Handle Problem Language Result Execution time Memory
962636 2024-04-14T05:05:10 Z Stiff Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 153348 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define shadow ios::sync_with_stdio(false), cin.tie(0)
using namespace std;

const ll INF = 1e18;
const int N = 2e5+7;

/*
A-->0
G-->1
C-->2
U-->3
*/

int n, m;
vector<int> permut[2], ord[2];

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

struct Trie{
    struct node{
        vector<int> pos;
        ll nxt[4]={-1, -1, -1, -1};
        int l = -1, r = -1;
        // node(int k){

        // }
    }org;


    vector<node> vec;
    Trie(){
        vec.push_back(org);
    }
    
    int len=1;

    void add_str(int cur, int k, int id, string s){
        if(vec[cur].nxt[trans(s[k])]==-1){
            vec[cur].nxt[trans(s[k])]=len;
            len++;
            vec.push_back(org);
        }
        cur=vec[cur].nxt[trans(s[k])];
        if(k==s.size()-1){
            vec[cur].pos.push_back(id);
            return;
        }
        add_str(cur, k+1, id, s);
    }

    pii init_order(int k, int idx){
        for(auto i:vec[idx].pos){
            permut[k].push_back(i);
            ord[k][i] = permut[k].size()-1;
        }
        int lt=-1;
        if(vec[idx].pos.size()){
            vec[idx].l=vec[idx].pos[0];
            vec[idx].r=vec[idx].pos[vec[idx].pos.size()-1];
            lt=vec[idx].pos[0];
        }
        
        for(int i=0;i<4;i++){
            if(vec[idx].nxt[i]!=-1){
                pii a = init_order(k, vec[idx].nxt[i]);
                vec[idx].r = a.second;
                if(lt==-1){
                    lt=a.first;
                }
            }
        }
        vec[idx].l=lt;
        return {vec[idx].l, vec[idx].r};
    }

    pii find_range(int cur, int k, string s){
        //cout<<cur<<' '<<k<<' '<<s<<endl;
        if(k==s.size()){
            return {vec[cur].l, vec[cur].r};
        }
        if(vec[cur].nxt[trans(s[k])]==-1){
            return {-1, -1};
        }
        cur = vec[cur].nxt[trans(s[k])];
        
        return find_range(cur, k+1, s);
    }

    void print(int idx){
        cout<<idx<<":\n";
        for(auto i:vec[idx].pos){
            cout<<i<<' ';
        }
        cout<<'\n';
        for(int i=0;i<4;i++){
            cout<<vec[idx].nxt[i]<<' ';
        }
        cout<<'\n';
        cout<<vec[idx].l<<' '<<vec[idx].r<<'\n';
        cout<<"\n";
        for(int i=0;i<4;i++){
            if(vec[idx].nxt[i]!=-1)
                print(vec[idx].nxt[i]);
        }
    }

}trie[2];


int main(){
    shadow;
    cin>>n>>m;
    ord[0].resize(n+1);
    ord[1].resize(n+1);
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        trie[0].add_str(0, 0, i+1, s);
        reverse(s.begin(), s.end());
        trie[1].add_str(0, 0, i+1, s);
    }
    
    trie[0].init_order(0, 0);
    trie[1].init_order(1, 0);
    //trie[0].print(0);
    string p, q;
    pii rg[2], a = {-1, -1};
    for(int i=0;i<m;i++){
        map<int, int> mp;
        cin>>p>>q;
        reverse(q.begin(), q.end());
        rg[0] = trie[0].find_range(0, 0, p);
        rg[1] = trie[1].find_range(0, 0, q);
        
        if(rg[0]== a||rg[1]==a)
            cout<<0<<'\n';
        else{
            for(int i = 0;i<2;i++){
                //cout<<rg[i].first<<' '<<rg[i].second<<'\n';
                for(int j=ord[i][rg[i].first];j<=ord[i][rg[i].second];j++){
                    mp[permut[i][j]]++;
                }
            }
            int ans=0;
            for(auto i:mp){
                if(i.second==2)
                    ans++;
            }
            cout<<ans<<'\n';
        }
    }
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add_str(int, int, int, std::string)':
selling_rna.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(k==s.size()-1){
      |            ~^~~~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::find_range(int, int, std::string)':
selling_rna.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if(k==s.size()){
      |            ~^~~~~~~~~~
selling_rna.cpp: In function 'int trans(char)':
selling_rna.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 452 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 153348 KB Output is correct
2 Execution timed out 1551 ms 138256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1533 ms 3244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 452 KB Output is correct
8 Correct 1464 ms 153348 KB Output is correct
9 Execution timed out 1551 ms 138256 KB Time limit exceeded
10 Halted 0 ms 0 KB -