제출 #546606

#제출 시각아이디문제언어결과실행 시간메모리
546606DeepessonSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
717 ms909876 KiB
#include <bits/stdc++.h> #define MAX 80005000 int N,Q; using ll = long long; const ll MOD = 998244353; typedef std::array<std::array<ll,2>,2> matriz; matriz mul(matriz a,matriz b){ matriz c={}; for(int i=0;i!=2;++i){ for(int j=0;j!=2;++j){ for(int k=0;k!=2;++k){ c[i][j]=(c[i][j]+(a[i][k]*b[k][j]))%MOD; } } } return c; } int get_num(char ch){ switch(ch){ case 'A': return 0; case 'G': return 1; case 'C': return 2; case 'U': return 3; } } int filhos[MAX][4]; int valor[2005000]; std::string str[2005000]; int freq[MAX]; int cur=2; int alocar(void){ return cur++; } void explora(std::deque<char> dek,std::string bet){ int inicio = 1; while(dek.size()){ int& ref = filhos[inicio][get_num(dek.front())]; if(!ref)ref=alocar(); inicio=ref; dek.pop_front(); } freq[inicio]++; str[inicio]=bet; } std::deque<char> gera_dek(std::string s){ std::deque<char> dek; for(auto&x:s)dek.push_back(x); return dek; } matriz neutro; matriz gera_mat(int B){ matriz c={}; c[0][0]=7; c[1][0]=B+2; c[1][1]=1; return c; } int mat[2005000*4]; std::string alvo; void update(int t,int b,int la=0,int ra=2005000-1,int pos=1){ if(!mat[pos])mat[pos]=alocar(); { int inicio = mat[pos]; for(int i=0;i!=alvo.size();++i){ auto&ref=filhos[inicio][get_num(alvo[i])]; if(!ref)ref=alocar(); freq[inicio]+=b; inicio=ref; } freq[inicio]+=b; } if(la==ra)return; int m = (la+ra)/2; if(t<=m) update(t,b,la,m,pos*2); if(t>m) update(t,b,m+1,ra,(pos*2)+1); } std::string analisa; int query(int l,int r,int la=0,int ra=2005000-1,int pos=1){ if(ra<l||la>r)return 0; if(la>=l&&ra<=r){ if(!mat[pos])return 0; int inicio = mat[pos]; for(int i=0;i!=analisa.size();++i){ auto&ref=filhos[inicio][get_num(analisa[i])]; if(!ref)return 0; inicio=ref; } return freq[inicio]; } int m = (la+ra)/2; return query(l,r,la,m,pos*2) + query(l,r,m+1,ra,(pos*2)+1); } int tamanhos[MAX]; int cur2=1; int dfs(int node){ if(!node)return 0; assert(!valor[node]); assert(cur2<2005000&&node<2005000); valor[node]=cur2; int size=1; if(freq[node]){///Opa!!! alvo=str[node]; std::reverse(alvo.begin(),alvo.end()); update(cur2,freq[node]); } ++cur2; for(int i=0;i!=4;++i){ size+=dfs(filhos[node][i]); } tamanhos[node]=size; return size; } int main() { neutro[0][0]=neutro[1][1]=1; std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); std::cin >> N >> Q; for(int i=0;i!=N;++i){ std::string s; std::cin >> s; explora(gera_dek(s),s); } dfs(1); ///Processa for(int i=0;i!=Q;++i){ std::string l,r; std::cin >> l >> r; int inicio = 1; for(int i=0;i!=l.size();++i){ int p = get_num(l[i]); inicio = filhos[inicio][p]; if(!inicio){ std::cout<<"0\n"; goto prox; } } { int tam = tamanhos[inicio],pos=valor[inicio]; analisa=r;std::reverse(analisa.begin(),analisa.end()); int soma = query(pos,pos+tam-1); std::cout<<soma<<"\n"; } prox:{} } }

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void update(int, int, int, int, int)':
selling_rna.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i=0;i!=alvo.size();++i){
      |                     ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(int, int, int, int, int)':
selling_rna.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=0;i!=analisa.size();++i){
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int i=0;i!=l.size();++i){
      |                     ~^~~~~~~~~~
selling_rna.cpp: In function 'int get_num(char)':
selling_rna.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...