Submission #1019646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019646		NintsiChkhaidze	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	362 ms	372236 KiB

selling_rna

#include <bits/stdc++.h>
#include <istream>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
// #define int ll
using namespace std;

const int N = 2e6 + 5;
string s[N];
map <int,int> mp;
int r1[N],r2[N];
int t[N][5],cnt1 = 1,cnt2 = 1,timer1,tin1[N],tout1[N];
int timer2,tin2[N],tout2[N],S[N][5];
vector <pii> vec1,vec2;
vector <int> arr[N],T[4*N];

void add1(string str,int id){
  int root = 1;
  for (int i = 0; i < str.size(); i++){
    int b = mp[str[i]];
    if (!t[root][b]){
      t[root][b] = ++cnt1;
    }

    root = t[root][b];
  }

  r1[id] = root;
}

int getprefix(string str){
  int root = 1;
  for (int i = 0; i < str.size(); i++){
    int b = mp[str[i]];
    if (!t[root][b]) return -1;
    root = t[root][b];
  }
  return root;
}

int getsuffix(string str){
  int root = 1;
  for (int i = 0; i < str.size(); i++){
    int b = mp[str[i]];
    if (!S[root][b]) return -1;
    root = S[root][b];
  }
  return root;
}

void add2(string str,int id){
  int root = 1;
  for (int i = 0; i < str.size(); i++){
    int b = mp[str[i]];
    if (!S[root][b]){
      S[root][b] = ++cnt2;
    }
    root = S[root][b];
  }

  r2[id] = root;
}

void dfs1(int x){
  tin1[x] = ++timer1;
  for (int i = 1; i <= 4; i++){
    if (t[x][i]) dfs1(t[x][i]);
  }
  tout1[x] = timer1;
}

void dfs2(int x){
  tin2[x] = ++timer2;
  for (int i = 1; i <= 4; i++){
    if (S[x][i]) dfs2(S[x][i]);
  }
  tout2[x] = timer2;
}

vector <int> merge(vector <int> x, vector <int> y){
  vector <int> ans;
  if (!x.size()) return y;
  if (!y.size()) return x;
  int l1 = 0,l2 = 0;
  while (l1 < x.size() || l2 < y.size()){
    if (l1==x.size()){
      ans.pb(y[l2++]);
      continue;
    }
    if (l2 == y.size()){
      ans.pb(x[l1++]);
      continue;
    }

    if (x[l1] < y[l2]){
      ans.pb(x[l1++]);
    }else{
      ans.pb(y[l2++]);
    }
  }
  return ans;
}

void build(int h,int l,int r){
  if (l == r){
    T[h] = arr[l];
    return;
  }

  build(left);
  build(right);
  T[h] = merge(T[h*2],T[h*2+1]);
}

int get(int h,int l,int r,int L,int R,int l2,int r2){
  if (r < L || R < l) return 0;
  if (L <= l && r <= R){
    int res1 = -1,le = 0,ri = T[h].size() - 1;
    while (le <= ri){
      int mid = (le + ri) / 2;
      if (T[h][mid] >= l2) {
        res1 = mid;
        ri = mid - 1;
      }else{
        le = mid + 1;
      }
    }
    if(res1==-1) return 0;

    int res2=-1; le = 0; ri = T[h].size() - 1;
    while (le <= ri){
      int mid = (le + ri) / 2;
      if (T[h][mid] <= r2) {
        res2 = mid;
        le = mid + 1;
      }else{
        ri = mid - 1;
      }
    }
    if(res2==-1) return 0;

    return (res2 - res1 + 1);
  }

  return get(left,L,R,l2,r2) + get(right,L,R,l2,r2);
}

signed main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

  mp['A'] = 1;
  mp['C'] = 2;
  mp['G'] = 3;
  mp['U'] = 4;

  int n,m;
  cin>>n>>m;

  for (int i = 1; i <= n; i++){
    cin >> s[i];
    add1(s[i],i);
    reverse(s[i].begin(),s[i].end());
    add2(s[i],i);
  }

  dfs1(1);
  dfs2(1);

  for (int i = 1; i <= n; i++){
    arr[tin2[r2[i]]].pb(tin1[r1[i]]);
  }

  int mm = tout2[1];
  for (int i = 1; i <= mm; i++){
    sort(arr[i].begin(),arr[i].end());
  }
  
  build(1,1,mm);

  for (int i = 1; i <= m; i++){
    string x,y;
    cin>>x>>y;

    int A = getprefix(x);
    if (A == -1) {
      cout<<0<<endl;
      continue;
    }
    int l1 = tin1[A],r1 = tout1[A];

    reverse(y.begin(),y.end());
    int B = getsuffix(y);
    if (B == -1){
      cout<<0<<endl;
      continue;
    }
    int l2 = tin2[B],r2 = tout2[B];
    cout<<get(1,1,mm,l2,r2,l1,r1)<<endl;
  }
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add1(std::string, int)':
selling_rna.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (int i = 0; i < str.size(); i++){
      |                   ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int getprefix(std::string)':
selling_rna.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int i = 0; i < str.size(); i++){
      |                   ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int getsuffix(std::string)':
selling_rna.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < str.size(); i++){
      |                   ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void add2(std::string, int)':
selling_rna.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int i = 0; i < str.size(); i++){
      |                   ~~^~~~~~~~~~~~
selling_rna.cpp: In function 'std::vector<int> merge(std::vector<int>, std::vector<int>)':
selling_rna.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   while (l1 < x.size() || l2 < y.size()){
      |          ~~~^~~~~~~~~~
selling_rna.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   while (l1 < x.size() || l2 < y.size()){
      |                           ~~~^~~~~~~~~~
selling_rna.cpp:92:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     if (l1==x.size()){
      |         ~~^~~~~~~~~~
selling_rna.cpp:96:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     if (l2 == y.size()){
      |         ~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40