Submission #1208427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208427		minhpk	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	609 ms	463172 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,q;
int child[2000001][26];
string z[100005];
int cnt;
int mark[1000005];
int tour;
int sta[1000005];
int fin[1000005];
int ver[1000005];
vector<pair<int,int>> m;
int mod=1e9+7;
int base=31;

bool cmp(pair<int,int> a,pair<int,int> b){
     if (a.first==b.first){
         return a.second<b.second;
     }
     return a.first<b.first;
}


void add(string& s,int pos){
    int k=0;
    for (auto c:s){
         if (!child[k][c-'A']){
             cnt++;
             child[k][c-'A']=cnt;
         }
         k=child[k][c-'A'];
    }
    mark[pos]=k;
}

void dfs(int k){
    tour++;
    sta[k]=tour;
    ver[tour]=k;

    for (int i=0;i<26;i++){
         if (child[k][i]){
             dfs(child[k][i]);
         }
    }

    fin[k]=tour;
}

int get(string& s,long long val){
    int k=0;

    for (auto c:s){
         if (!child[k][c-'A']){
              return 0;
         }
         k=child[k][c-'A'];
    }
 //   cout << "ok" << "\n";
   // cout << m[val].size() << "\n";
    int pos=sta[k];
    int l=lower_bound(m.begin(),m.end(),make_pair(val,pos))-m.begin();
    pos=fin[k];
    int r=upper_bound(m.begin(),m.end(),make_pair(val,pos))-m.begin()-1;
    return r-l+1;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> q;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         add(z[i],i);
    }
    dfs(0);
    for (int i=1;i<=a;i++){
         long long h=0;
         int pos=mark[i];
         pos=sta[pos];
         for (int j=z[i].size()-1;j>=0;j--){
             h=(h*base + (z[i][j]-'A'+1))%mod;
           //  cout << h << " ";
             m.push_back({h,pos});
         }
    }


    sort(m.begin(),m.end(),cmp);


    while (q--){
        string s,s1;
        cin >> s >> s1;
        long long h=0;
        for (int i=s1.size()-1;i>=0;i--){
             h=(h*base + (s1[i]-'A'+1))%mod;
        }
       // cout << h << " ";
        cout <<  get(s,h) << "\n";
    }
    return 0;
}

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