Submission #788698

#TimeUsernameProblemLanguageResultExecution timeMemory
788698Dan4LifeSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
343 ms205308 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) begin(a),end(a) const int mxN = (int)1e5+10; const int mxS = (int)2e6+10; vector<int> xd[mxS]; int trie[2][4][mxS]; int L[mxS], R[mxS]; int n, m, node[2]; string s[mxS]; void add(string &s, int ind, int t){ int v = 1; for(auto u : s){ int c = (u=='A'?0:u=='C'?1:u=='G'?2:3); if(!trie[t][c][v]) trie[t][c][v]=node[t]++; v = trie[t][c][v]; if(!t){ if(!L[v]) L[v]=ind; R[v]=max(R[v],ind); } else xd[v].pb(ind); } } int get(string &s, int t){ int v = 1; for(auto u : s){ int c = (u=='A'?0:u=='C'?1:u=='G'?2:3); v = trie[t][c][v]; if(!v) return 0; } return v; } int32_t main() { cin >> n >> m; node[0]=node[1]=2; for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n); for(int i = 0; i < n; i++) add(s[i],i+1,0),reverse(all(s[i])),add(s[i],i+1,1); for(int i = 0; i < m; i++){ string s, t; cin >> s >> t; reverse(all(t)); int ind = get(s,0), ind2=get(t,1); int l = L[ind], r=R[ind]; if(!l or !ind or !ind2) { cout << "0\n"; continue; } int pos1 = lower_bound(all(xd[ind2]),l)-begin(xd[ind2]); int pos2 = upper_bound(all(xd[ind2]),r)-begin(xd[ind2]); cout << max(0, pos2-pos1) << "\n"; } }

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:39:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   39 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |  ^~~
selling_rna.cpp:39:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  for(int i = 0; i < n; i++) cin >> s[i]; sort(s,s+n);
      |                                          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...