oj.uz

Submission #546604

# Submission time Handle Problem Language Result Execution time Memory
546604 2022-04-07T21:10:37 Z Deepesson Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 679 ms 911960 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){
    if(cur==MAX){
        std::cout<<"oops\n";
        exit(0);
    }
    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]++;
    assert(inicio<2005000);
    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:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0;i!=alvo.size();++i){
      |                     ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(int, int, int, int, int)':
selling_rna.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i=0;i!=analisa.size();++i){
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         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 31 ms 63200 KB Output is correct
2 Correct 32 ms 63248 KB Output is correct
3 Correct 31 ms 63184 KB Output is correct
4 Correct 33 ms 63136 KB Output is correct
5 Correct 32 ms 63196 KB Output is correct
6 Correct 29 ms 63148 KB Output is correct
7 Correct 28 ms 63264 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 911960 KB Output is correct
2 Correct 627 ms 871024 KB Output is correct
3 Correct 589 ms 610696 KB Output is correct
4 Correct 549 ms 565208 KB Output is correct
5 Correct 501 ms 641540 KB Output is correct
6 Correct 514 ms 649924 KB Output is correct
7 Correct 583 ms 129780 KB Output is correct
8 Correct 623 ms 713972 KB Output is correct
9 Correct 558 ms 608692 KB Output is correct
10 Correct 396 ms 449212 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63472 KB Output is correct
2 Correct 51 ms 65404 KB Output is correct
3 Correct 55 ms 64516 KB Output is correct
4 Correct 45 ms 63260 KB Output is correct
5 Correct 53 ms 64588 KB Output is correct
6 Correct 55 ms 64128 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63200 KB Output is correct
2 Correct 32 ms 63248 KB Output is correct
3 Correct 31 ms 63184 KB Output is correct
4 Correct 33 ms 63136 KB Output is correct
5 Correct 32 ms 63196 KB Output is correct
6 Correct 29 ms 63148 KB Output is correct
7 Correct 28 ms 63264 KB Output is correct
8 Correct 679 ms 911960 KB Output is correct
9 Correct 627 ms 871024 KB Output is correct
10 Correct 589 ms 610696 KB Output is correct
11 Correct 549 ms 565208 KB Output is correct
12 Correct 501 ms 641540 KB Output is correct
13 Correct 514 ms 649924 KB Output is correct
14 Correct 583 ms 129780 KB Output is correct
15 Correct 623 ms 713972 KB Output is correct
16 Correct 558 ms 608692 KB Output is correct
17 Correct 396 ms 449212 KB Output is correct
18 Correct 63 ms 63472 KB Output is correct
19 Correct 51 ms 65404 KB Output is correct
20 Correct 55 ms 64516 KB Output is correct
21 Correct 45 ms 63260 KB Output is correct
22 Correct 53 ms 64588 KB Output is correct
23 Correct 55 ms 64128 KB Output is correct
24 Correct 549 ms 761860 KB Output is correct
25 Correct 553 ms 761784 KB Output is correct
26 Correct 551 ms 753444 KB Output is correct
27 Correct 522 ms 471664 KB Output is correct
28 Correct 204 ms 160036 KB Output is correct
29 Correct 93 ms 66960 KB Output is correct