제출 #546606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546606		Deepesson	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	717 ms	909876 KiB

selling_rna

#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 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40