제출 #546579

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

selling_rna

#include <bits/stdc++.h>
#define MAX 2005000
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[MAX];
std::string str[MAX];
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;
}
std::map<matriz,int> mat[MAX*4];
void update(int t,matriz k,int b,int la=0,int ra=MAX-1,int pos=1){
    if(ra<t||la>t)return;
    mat[pos][k]+=b;
    if(la==ra)return;
    int m = (la+ra)/2;
    update(t,k,b,la,m,pos*2);
    update(t,k,b,m+1,ra,(pos*2)+1);
}
int query(int l,int r,matriz k,int la=0,int ra=MAX-1,int pos=1){
    if(ra<l||la>r)return 0;
    if(la>=l&&ra<=r){
        auto ref = mat[pos].find(k);
        if(ref==mat[pos].end())return 0;
        return ref->second;
    }
    int m = (la+ra)/2;
    return query(l,r,k,la,m,pos*2) + query(l,r,k,m+1,ra,(pos*2)+1);
}
int tamanhos[MAX];
int cur2=1;
int dfs(int node){
    if(!node)return 0;
    assert(!valor[node]);
    valor[node]=cur2;
    int size=1;
    if(freq[node]){///Opa!!!
        matriz bas = neutro;
        for(int i=str[node].size()-1;i!=-1;--i){
            bas=mul(gera_mat(get_num(str[node][i])),bas);
            update(cur2,bas,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);
    return 0;
    ///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];
            matriz bas = neutro;
            for(int i=r.size()-1;i!=-1;--i){
                bas=mul(gera_mat(get_num(r[i])),bas);
            }
            int soma = query(pos,pos+tam-1,bas);
            std::cout<<soma<<"\n";
        }
        prox:{}
    }
}

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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         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: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40