oj.uz

Submission #546606

# Submission time Handle Problem Language Result Execution time Memory
546606 2022-04-07T21:17:49 Z Deepesson Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 717 ms 909876 KB 
#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:{}
    }
}

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: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63180 KB Output is correct
2 Correct 32 ms 63272 KB Output is correct
3 Correct 28 ms 63188 KB Output is correct
4 Correct 29 ms 63180 KB Output is correct
5 Correct 28 ms 63188 KB Output is correct
6 Correct 28 ms 63188 KB Output is correct
7 Correct 30 ms 63248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 909876 KB Output is correct
2 Correct 602 ms 867088 KB Output is correct
3 Correct 601 ms 606720 KB Output is correct
4 Correct 567 ms 561412 KB Output is correct
5 Correct 501 ms 638920 KB Output is correct
6 Correct 534 ms 647540 KB Output is correct
7 Correct 592 ms 124552 KB Output is correct
8 Correct 644 ms 708136 KB Output is correct
9 Correct 540 ms 602800 KB Output is correct
10 Correct 411 ms 445944 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63472 KB Output is correct
2 Correct 51 ms 65412 KB Output is correct
3 Correct 57 ms 64444 KB Output is correct
4 Correct 46 ms 63308 KB Output is correct
5 Correct 57 ms 64580 KB Output is correct
6 Correct 71 ms 64020 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63180 KB Output is correct
2 Correct 32 ms 63272 KB Output is correct
3 Correct 28 ms 63188 KB Output is correct
4 Correct 29 ms 63180 KB Output is correct
5 Correct 28 ms 63188 KB Output is correct
6 Correct 28 ms 63188 KB Output is correct
7 Correct 30 ms 63248 KB Output is correct
8 Correct 717 ms 909876 KB Output is correct
9 Correct 602 ms 867088 KB Output is correct
10 Correct 601 ms 606720 KB Output is correct
11 Correct 567 ms 561412 KB Output is correct
12 Correct 501 ms 638920 KB Output is correct
13 Correct 534 ms 647540 KB Output is correct
14 Correct 592 ms 124552 KB Output is correct
15 Correct 644 ms 708136 KB Output is correct
16 Correct 540 ms 602800 KB Output is correct
17 Correct 411 ms 445944 KB Output is correct
18 Correct 54 ms 63472 KB Output is correct
19 Correct 51 ms 65412 KB Output is correct
20 Correct 57 ms 64444 KB Output is correct
21 Correct 46 ms 63308 KB Output is correct
22 Correct 57 ms 64580 KB Output is correct
23 Correct 71 ms 64020 KB Output is correct
24 Correct 545 ms 757776 KB Output is correct
25 Correct 569 ms 757648 KB Output is correct
26 Correct 550 ms 749516 KB Output is correct
27 Correct 513 ms 467660 KB Output is correct
28 Correct 216 ms 155700 KB Output is correct
29 Correct 96 ms 63772 KB Output is correct