oj.uz

답안 #546586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546586 2022-04-07T20:57:01 Z Deepesson Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 529 ms 837784 KB 
#include <bits/stdc++.h>
#define MAX 10005000
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;
}
int mat[MAX*4];
std::string alvo;
void update(int t,int b,int la=0,int ra=MAX-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=MAX-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]);
    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:{}
    }
}

Compilation message

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:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 313700 KB Output is correct
2 Correct 134 ms 313668 KB Output is correct
3 Correct 153 ms 313712 KB Output is correct
4 Correct 147 ms 313768 KB Output is correct
5 Correct 134 ms 313764 KB Output is correct
6 Correct 139 ms 313756 KB Output is correct
7 Correct 140 ms 313756 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 529 ms 837784 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 314300 KB Output is correct
2 Correct 166 ms 316388 KB Output is correct
3 Correct 197 ms 315376 KB Output is correct
4 Correct 167 ms 313988 KB Output is correct
5 Correct 166 ms 315236 KB Output is correct
6 Correct 185 ms 314772 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 313700 KB Output is correct
2 Correct 134 ms 313668 KB Output is correct
3 Correct 153 ms 313712 KB Output is correct
4 Correct 147 ms 313768 KB Output is correct
5 Correct 134 ms 313764 KB Output is correct
6 Correct 139 ms 313756 KB Output is correct
7 Correct 140 ms 313756 KB Output is correct
8 Runtime error 529 ms 837784 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -