Submission #1208428

#TimeUsernameProblemLanguageResultExecution timeMemory
1208428minhpkSelling RNA Strands (JOI16_selling_rna)C++20
35 / 100
284 ms68748 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,q; int child[2000001][26]; string z[1000005]; 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=43; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...