Submission #897460

#	Time	Username	Problem	Language	Result	Execution time	Memory
897460		dwuy	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	215 ms	203300 KiB

selling_rna

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MX = 100005;
int n, q;
int ans[MX];
string a[MX];
tuple<string, string, int> queries[MX];

void nhap(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=q; i++){
        string p, q;
        cin >> p >> q;
        queries[i] = {p, q, i};
    }
}

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

struct Node{
    vector<int> id;
    Node *child[4];

    Node(){
        this->id.clear();
        for(int t=4; t--;) this->child[t] = NULL;
    }
};

Node *root = new Node();

void add(string s, int id){
    reverse(s.begin(), s.end());
    Node *cur = root;
    for(char c: s){
        int t = cv(c);
        if(cur->child[t] == NULL) cur->child[t] = new Node();
        cur = cur->child[t];
        cur->id.push_back(id);
    }
}

void solve(){
    sort(a+1, a+1+n);
    sort(queries+1, queries+1+q);

    for(int i=1; i<=n; i++) add(a[i], i);

    a[0] = "";
    a[n+1] = "~";
    for(int i=1; i<=q; i++){
        string pf, sf; int id;
        tie(pf, sf, id) = queries[i];
        reverse(sf.begin(), sf.end());
        Node *cur = root;
        for(char c: sf){
            int t = cv(c);
            if(cur->child[t] == NULL){
                ans[id] = -1;
                break;
            }
            cur = cur->child[t];
        }
        #define all(x) (x).begin(),(x).end()
        if(ans[id] == -1) ans[id] = 0;
        else {
            int fx = cur->id.size();
            for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
                int mid = (lo+hi)>>1;
                int p = cur->id[mid];
                if(a[p] >= pf) fx = mid, hi = mid - 1;
                else lo = mid + 1;
            }
            int fy = cur->id.size();
            for(int lo=0, hi=(int)cur->id.size() - 1; lo<=hi;){
                int mid = (lo+hi)>>1;
                int p = cur->id[mid];
                if(a[p] > pf+"}") fy = mid , hi = mid - 1;
                else lo = mid + 1;
            }
            ans[id] = fy - fx;
        }
    }
    for(int i=1; i<=q; i++) cout << ans[i] << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

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