Submission #1106557

#TimeUsernameProblemLanguageResultExecution timeMemory
1106557ntdaccodeSelling RNA Strands (JOI16_selling_rna)C++17
35 / 100
88 ms92488 KiB
#include<bits/stdc++.h> #define fori(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef pair<int,int> ii; typedef tuple<int,int,int> tp; const int M=1e5+10; const int N=245000; const int mod=1e9+7; int n,m; int ch[N][26],ch2[N][26]; int l[N],r[N]; vector<int> suf[N]; int cnt=0,cnt2=0; void upd(string &s,int &node) { int idx=0; int sz=s.size()-1; fori(i,0,sz) { int k=s[i]-'A'; if(!ch[idx][k]) { ch[idx][k]=++cnt; l[cnt]=1e9; r[cnt]=0; } idx=ch[idx][k]; l[idx]=min(l[idx],node); r[idx]=max(r[idx],node); } } void upd2(string &s,int &node) { int idx=0; int sz=s.size()-1; fori(i,0,sz) { int k=s[i]-'A'; if(!ch2[idx][k]) ch2[idx][k]=++cnt2; idx=ch2[idx][k]; suf[idx].push_back(node); } } ii get(string &s) { int idx=0; int sz=s.size()-1; fori(i,0,sz) { int k=s[i]-'A'; if(!ch[idx][k]) return {0,0}; idx=ch[idx][k]; } return {l[idx],r[idx]}; } int get2(string &s,int &u,int &v) { int idx=0; int sz=s.size()-1; fori(i,0,sz) { int k=s[i]-'A'; if(!ch2[idx][k]) return 0; idx=ch2[idx][k]; } int uu=lower_bound(suf[idx].begin(),suf[idx].end(),u)-suf[idx].begin(); int vv=upper_bound(suf[idx].begin(),suf[idx].end(),v)-suf[idx].begin(); return vv-uu; } string s[M]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen("1.inp","r")) { freopen("1.inp","r",stdin); freopen("1.out","w",stdout); } #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> m; fori(i,1,n) cin >> s[i]; sort(s+1,s+n+1); fori(i,1,n){ upd(s[i],i); reverse(s[i].begin(),s[i].end()); upd2(s[i],i); } while(m--) { string pre,suf; cin >> pre >> suf; reverse(suf.begin(),suf.end()); auto [u,v] = get(pre); if(u==0&&v==0) cout << 0 << "\n"; else cout << get2(suf,u,v) << "\n"; } }

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...