Submission #972554

#	Time	Username	Problem	Language	Result	Execution time	Memory
972554		duckindog	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1520 ms	78416 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

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

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];

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

int it;
void mark(const auto& s) { 
  int g = 0;
  for (int i = 1; i <= 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(const auto& s, int id) { 
  int g = 0;
  for (int i = 1; i <= s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
    if (mk[g]) vt[g].push_back(id);
  }
}
int get(const auto& s, Hash e) { 
  int g = 0;
  for (int i = 1; i <= s.size(); ++i) { 
    int path = convert(s[i - 1]);
    if (!nwt[g][path]) nwt[g][path] = ++it;
    g = nwt[g][path];
  }

  int ret = 0;
  for (const auto& id : vt[g]) {
    if (h[id].n < e.n) continue;
    ret += (h[id].get(h[id].n - e.n + 1, h[id].n) == e.get(1, e.n));
  }
  return ret;
}



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

  cin >> n >> m;
  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) { 
    h[i] = Hash(str[i]);
    add(str[i], i);
  }

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

Compilation message (stderr)

selling_rna.cpp:28:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   28 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
      |                   ^~~~
selling_rna.cpp:34:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   34 | void mark(const auto& s) {
      |                 ^~~~
selling_rna.cpp:43:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   43 | void add(const auto& s, int id) {
      |                ^~~~
selling_rna.cpp:52:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   52 | int get(const auto& s, Hash e) {
      |               ^~~~
selling_rna.cpp: In instantiation of 'void mark(const auto:24&) [with auto:24 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:77:42:   required from here
selling_rna.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (int i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'void add(const auto:25&, int) [with auto:25 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:80:18:   required from here
selling_rna.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'int get(const auto:26&, Hash) [with auto:26 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:83:62:   required from here
selling_rna.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 1; i <= s.size(); ++i) {
      |                   ~~^~~~~~~~~~~

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