oj.uz

답안 #546576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546576 2022-04-07T20:42:14 Z Deepesson Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 655580 KB 
#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;
   /// std::cout<<"add "<<la<<" "<<ra<<" "<<b<<"\n";
    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){
      ///  std::cout<<"pega "<<la<<" "<<ra<<"\n";
        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]);
    ///std::cout<<"Nov "<<node<<" "<<cur2<<"!!!\n";
    valor[node]=cur2;
    int size=1;
    if(freq[node]){///Opa!!!
      ///  std::cout<<"Upd "<<node<<" "<<cur2<<" "<<str[node]<<" "<<freq[node]<<"\n";
        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]);
            ///for(int i=0;i!=2;++i){
            ///    for(int j=0;j!=2;++j){
            ///        std::cout<<bas[i][j]<<" ";
           ///     }
          ///      std::cout<<"\n";
          ///  }
          ///  std::cout<<"\n";
        }
    }
    ++cur2;
    for(int i=0;i!=4;++i){
        size+=dfs(filhos[node][i]);
    }
    tamanhos[node]=size;
   /// std::cout<<"Size "<<size<<"->"<<node<<"\n";
    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;
            }
        }
      ///  std::cout<<"ok "<<inicio<<"\n";
        {
            int tam = tamanhos[inicio],pos=valor[inicio];
           /// std::cout<<"! "<<tam<<" "<<pos<<"\n";
            matriz bas = neutro;
            for(int i=r.size()-1;i!=-1;--i){
                bas=mul(gera_mat(get_num(r[i])),bas);
            }
           /// for(int i=0;i!=2;++i){
          ///      for(int j=0;j!=2;++j){
          ///          std::cout<<bas[i][j]<<" ";
         ///       }
        ///        std::cout<<"\n";
         ///   }
         ///   std::cout<<"\n";
          ///  std::cout<<pos<<" "<<pos+tam-1<<"<<<\n";
            int soma = query(pos,pos+tam-1,bas);
            std::cout<<soma<<"\n";
        }
        prox:{}
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         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 232 ms 440016 KB Output is correct
2 Correct 218 ms 440052 KB Output is correct
3 Correct 243 ms 440012 KB Output is correct
4 Correct 240 ms 440000 KB Output is correct
5 Correct 219 ms 439992 KB Output is correct
6 Correct 255 ms 439960 KB Output is correct
7 Correct 220 ms 440088 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1626 ms 655580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 440448 KB Output is correct
2 Correct 340 ms 448744 KB Output is correct
3 Correct 353 ms 444908 KB Output is correct
4 Correct 283 ms 440320 KB Output is correct
5 Correct 371 ms 444628 KB Output is correct
6 Correct 310 ms 443068 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 440016 KB Output is correct
2 Correct 218 ms 440052 KB Output is correct
3 Correct 243 ms 440012 KB Output is correct
4 Correct 240 ms 440000 KB Output is correct
5 Correct 219 ms 439992 KB Output is correct
6 Correct 255 ms 439960 KB Output is correct
7 Correct 220 ms 440088 KB Output is correct
8 Execution timed out 1626 ms 655580 KB Time limit exceeded
9 Halted 0 ms 0 KB -