oj.uz

Submission #972579

# Submission time Handle Problem Language Result Execution time Memory
972579 2024-04-30T16:27:08 Z duckindog Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m;
string str[N];
string st[N], ed[N];

int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
int nwt[N << 2][4];
bool mk[N << 2];

struct Trie {
  int it;
  vector<array<int, 4>> nwt;
  vector<int> sz;
 
  Trie() : nwt(1), sz(1) {}

  void add(string s) {
    int g = 0;
    for (int i = 1; i <= (int)s.size(); ++i) {
      while (nwt.size() <= g) nwt.push_back(array<int, 4>());

      int path = convert(s[i - 1]);
      if (!nwt[g][path]) nwt[g][path] = ++it;
      g = nwt[g][path];

      while (sz.size() <= it) sz.push_back(0);
      sz[g] += 1;
    }
  }

  int get(string s) { 
    int g = 0;
    for (int i = 1; i <= (int)s.size(); ++i) {
      int path = convert(s[i - 1]);
      if (!nwt[g][path]) return 0;
      g = nwt[g][path];
    }
    return sz[g];
  }
} T[N << 2];

int it;
void mark(string s) { 
  int g = 0;
  for (int i = 1; i <= (int)s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
  }
  mk[g] = true;
}
void add(string s) { 
  string rs = string(s.rbegin(), s.rend());
  int g = 0;
  for (int i = 1; i <= (int)s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
    if (mk[g]) T[g].add(rs);
  }
}

int get(string s, const auto& e) { 
  int g = 0;
  for (int i = 1; i <= (int)s.size(); ++i) { 
    int path = convert(s[i - 1]);
    g = nwt[g][path];
  }
  return T[g].get(string(e.rbegin(), e.rend()));
}

namespace sub2 { 
  const int base = 19937;
  using ull = unsigned long long;
  ull pw[N];
  struct Hash {
    int n;
    vector<ull> h;
  
    Hash() {}
    Hash(string s) : n(s.size()), h(s.size() + 1) { 
      pw[0] = 1;
      for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * base + s[i - 1];
        pw[i] = pw[i - 1] * base;
      }
    }
    ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
  } h[N];

  void solve() { 
    for (int i = 1; i <= n; ++i) { 
      string s; cin >> s;
      h[i] = Hash(s);
    }
 
    while (m--) { 
      string st, ed; cin >> st >> ed;
      
      Hash s(st), e(ed);
  
      int answer = 0;
      for (int i = 1; i <= n; ++i) { 
        if (h[i].n < s.n || h[i].n < e.n) continue;
  
        answer += (h[i].get(1, s.n) == s.get(1, s.n) 
                    && h[i].get(h[i].n - e.n + 1, h[i].n) == e.get(1, e.n));
      }
      cout << answer << "\n";
    }
  }

}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  if (n <= 5000 && m <= 5000) { sub2::solve(); return 0; }

  for (int i = 1; i <= n; ++i) cin >> str[i];
  for (int i = 1; i <= m; ++i) cin >> st[i] >> ed[i];

  for (int i = 1; i <= m; ++i) mark(st[i]);
  for (int i = 1; i <= n; ++i) add(str[i]);
  
  for (int i = 1; i <= m; ++i) cout << get(st[i], ed[i]) << "\n";
}

Compilation message

selling_rna.cpp:10:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
      |                   ^~~~
selling_rna.cpp: In member function 'void Trie::add(std::string)':
selling_rna.cpp:24:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |       while (nwt.size() <= g) nwt.push_back(array<int, 4>());
      |              ~~~~~~~~~~~^~~~
selling_rna.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |       while (sz.size() <= it) sz.push_back(0);
      |              ~~~~~~~~~~^~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:67:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   67 | int get(string s, const auto& e) {
      |                         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63160 KB Output is correct
2 Correct 33 ms 63068 KB Output is correct
3 Correct 34 ms 63296 KB Output is correct
4 Correct 33 ms 63320 KB Output is correct
5 Correct 34 ms 63060 KB Output is correct
6 Correct 33 ms 63072 KB Output is correct
7 Correct 32 ms 63056 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 82792 KB Output is correct
2 Correct 298 ms 83036 KB Output is correct
3 Correct 147 ms 82772 KB Output is correct
4 Correct 198 ms 83028 KB Output is correct
5 Correct 183 ms 75568 KB Output is correct
6 Correct 222 ms 75704 KB Output is correct
7 Correct 147 ms 80592 KB Output is correct
8 Correct 220 ms 84816 KB Output is correct
9 Correct 217 ms 84748 KB Output is correct
10 Correct 312 ms 82352 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 63836 KB Output is correct
2 Correct 54 ms 64596 KB Output is correct
3 Correct 55 ms 64088 KB Output is correct
4 Correct 43 ms 63568 KB Output is correct
5 Correct 50 ms 63828 KB Output is correct
6 Correct 54 ms 63800 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63160 KB Output is correct
2 Correct 33 ms 63068 KB Output is correct
3 Correct 34 ms 63296 KB Output is correct
4 Correct 33 ms 63320 KB Output is correct
5 Correct 34 ms 63060 KB Output is correct
6 Correct 33 ms 63072 KB Output is correct
7 Correct 32 ms 63056 KB Output is correct
8 Correct 109 ms 82792 KB Output is correct
9 Correct 298 ms 83036 KB Output is correct
10 Correct 147 ms 82772 KB Output is correct
11 Correct 198 ms 83028 KB Output is correct
12 Correct 183 ms 75568 KB Output is correct
13 Correct 222 ms 75704 KB Output is correct
14 Correct 147 ms 80592 KB Output is correct
15 Correct 220 ms 84816 KB Output is correct
16 Correct 217 ms 84748 KB Output is correct
17 Correct 312 ms 82352 KB Output is correct
18 Correct 48 ms 63836 KB Output is correct
19 Correct 54 ms 64596 KB Output is correct
20 Correct 55 ms 64088 KB Output is correct
21 Correct 43 ms 63568 KB Output is correct
22 Correct 50 ms 63828 KB Output is correct
23 Correct 54 ms 63800 KB Output is correct
24 Runtime error 1500 ms 1048576 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -