Submission #897466

#	Time	Username	Problem	Language	Result	Execution time	Memory
897466		dwuy	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	319 ms	598864 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';
}
 
struct Node{
    vector<int> id;
    Node *child[30];
 
    Node(){
        this->id.clear();
        for(int t=30; 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