Submission #905878

#	Time	Username	Problem	Language	Result	Execution time	Memory
905878		coldbr3w	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	497 ms	369816 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<long long, long long>;
 
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
struct Trie{
    struct node{
        ll c[4];
        ll l, r;
        vector<ll>range;
    }; node x[N];
    ll cur;
    Trie() : cur(0){
        memset(x[0].c, -1, sizeof(x[0].c));
        x[0].l = inf;
        x[0].r = -inf;
    }
    ll init(){
        cur++;
        memset(x[cur].c, -1, sizeof(x[cur].c));
        x[cur].l = inf, x[cur].r = -inf;
        return cur;
    }  
    void add(string s, ll idx){
        ll pos = 0;
        for(auto f : s){
            ll c = f - 'A';
            if(x[pos].c[c] == -1) x[pos].c[c] = init();
            pos = x[pos].c[c];
            x[pos].range.pb(idx);
            x[pos].l = min(idx, x[pos].l);
            x[pos].r = max(idx, x[pos].r);
        }
    }
    pll find_range(string s){
        ll pos = 0;
        for(auto f : s){
            ll c = f - 'A';
            pos = x[pos].c[c];
            if(pos == -1) return {inf, -inf};
        }
        return {x[pos].l, x[pos].r};
    }
    vector<ll>dfs(string s){
        ll pos = 0;
        vector<ll>tmp;
        for(auto f : s){
            ll c = f - 'A';
            pos = x[pos].c[c];
            if(pos == -1) return tmp;
        }
        return x[pos].range;
    }
};
string cnv(string s){
    string ans = s;
    for(int i = 0; i < ans.size();i++){
        if(ans[i] == 'C') ans[i] = 'B';
        else if(ans[i] == 'G') ans[i] = 'C';
        else if(ans[i] == 'U') ans[i] = 'D'; 
    }
    return ans;
}
Trie rev, tr;
void to_nho_cau(){
    ll n,m; cin >> n >> m;
    vector<string>v;
    for(int i = 1; i <= n;i++){
        string s; cin >> s;
        s = cnv(s);
        v.pb(s);
    }
    sort(all(v));
    for(int i = 0; i < v.size();i++){
        tr.add(v[i], i);
        string t = v[i]; reverse(all(t));
        rev.add(t, i);
    }
    while(m--){
        string p,q; cin >> p >> q;
        p = cnv(p), q = cnv(q);    
        reverse(all(q));
        pll cur = tr.find_range(p);
        ll l = cur.F, r = cur.S;
        vector<ll>res = rev.dfs(q);
        if(!res.size() || l > r){
            cout << 0 << '\n';
            continue;
        }
        ll high = upper_bound(all(res), r) - res.begin();
        ll low = lower_bound(all(res), l) - res.begin();
        cout << high - low << '\n';
    }
}
 
signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;   
    //cin >> t;
    while(t--) to_nho_cau();
}

Compilation message (stderr)

selling_rna.cpp: In function 'std::string cnv(std::string)':
selling_rna.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i = 0; i < ans.size();i++){
      |                    ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void to_nho_cau()':
selling_rna.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~

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