Submission #49994

#TimeUsernameProblemLanguageResultExecution timeMemory
49994MatheusLealVSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
401 ms185872 KiB
#include <bits/stdc++.h> #define N 2000050 #define f first #define s second using namespace std; typedef pair<int, int> pii; int getid(char c) { if(c == 'A') return 0; if(c == 'C') return 1; if(c == 'G') return 2; if(c == 'U') return 3; } struct node { int ini, fim; node *prox[4]; node(){ for(int i = 0; i < 4; i++) prox[i] = NULL; } } *T[2]; struct query { int x, y, x2, tipo, id; }; bool comp(query A, query B) { if(A.y != B.y) return A.y < B.y; return A.tipo < B.tipo; } vector< pii > pontos; vector< query > Q; int n, m, cnt, ans[N]; string S[N]; void insert(node *root, string key) { for(auto c: key) { int id = getid(c); if(!root->prox[id]) root->prox[id] = new node(); root = root->prox[id]; } } pii search(node *root, string key) { for(auto c: key) { int id = getid(c); if(!root->prox[id]) return {-1, -1}; root = root->prox[id]; } return {root->ini, root->fim}; } void dfs(node *root) { root->ini = ++cnt; for(int i = 0; i < 4; i++) { if(!root->prox[i]) continue; dfs(root->prox[i]); } root->fim = cnt; } int bit[N]; void upd(int x, int v) { for(int i = x; i < N; i += (i&-i)) bit[i] += v; } int query(int x) { int sum = 0; for(int i = x; i > 0; i -= (i&-i)) sum += bit[i]; return sum; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; T[0] = new node(), T[1] = new node(); for(int i = 0; i < n; i++) { cin>>S[i]; insert(T[0], S[i]); reverse(S[i].begin(), S[i].end()); insert(T[1], S[i]); } dfs(T[0]), dfs(T[1]); for(int i = 0; i < n; i++) { int b = search(T[1], S[i]).f; reverse(S[i].begin(), S[i].end()); int a = search(T[0], S[i]).f; Q.push_back( {a, b, a, 0, i} ); //cout<<"PONTO "<<a<<" "<<b<<"\n"; } for(int i = 0; i < m; i++) { string pref, suf; cin>>pref>>suf; reverse(suf.begin(), suf.end()); pii a = search(T[0], pref); pii b = search(T[1], suf); if(a.f == -1 || b.f == -1) continue; Q.push_back( {a.f, b.f - 1, a.s, 1, i} ); Q.push_back( {a.f, b.s, a.s, 2, i} ); //cout<<"QUERY "<<a.f<<" "<<a.s<<" "<<b.f<<" "<<b.s<<"\n"; } sort(Q.begin(), Q.end(), comp); for(int i = 0; i < Q.size(); i++) { if(!Q[i].tipo) upd(Q[i].x, +1); else { if(Q[i].tipo == 1) ans[ Q[i].id ] -= (query(Q[i].x2) - query(Q[i].x - 1)); else ans[ Q[i].id ] += (query(Q[i].x2) - query(Q[i].x - 1)); } } for(int i = 0; i < m; i++) cout<<ans[i]<<"\n"; }

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:161:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < Q.size(); i++)
                 ~~^~~~~~~~~~
selling_rna.cpp: In function 'int getid(char)':
selling_rna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...