oj.uz

Submission #972891

# Submission time Handle Problem Language Result Execution time Memory
972891 2024-05-01T09:40:45 Z duckindog Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1448 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 * 10][4];
bool mk[N * 10];
 
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 * 10];
 
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 93 ms 133200 KB Output is correct
2 Correct 91 ms 133452 KB Output is correct
3 Correct 75 ms 133376 KB Output is correct
4 Correct 82 ms 133908 KB Output is correct
5 Correct 75 ms 133444 KB Output is correct
6 Correct 75 ms 133200 KB Output is correct
7 Correct 76 ms 133448 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 153156 KB Output is correct
2 Correct 277 ms 153008 KB Output is correct
3 Correct 204 ms 153188 KB Output is correct
4 Correct 232 ms 153208 KB Output is correct
5 Correct 224 ms 145624 KB Output is correct
6 Correct 282 ms 146044 KB Output is correct
7 Correct 182 ms 150540 KB Output is correct
8 Correct 269 ms 155092 KB Output is correct
9 Correct 248 ms 154960 KB Output is correct
10 Correct 299 ms 152548 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 133968 KB Output is correct
2 Correct 105 ms 134736 KB Output is correct
3 Correct 106 ms 134276 KB Output is correct
4 Correct 86 ms 133972 KB Output is correct
5 Correct 107 ms 134224 KB Output is correct
6 Correct 126 ms 133968 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 133200 KB Output is correct
2 Correct 91 ms 133452 KB Output is correct
3 Correct 75 ms 133376 KB Output is correct
4 Correct 82 ms 133908 KB Output is correct
5 Correct 75 ms 133444 KB Output is correct
6 Correct 75 ms 133200 KB Output is correct
7 Correct 76 ms 133448 KB Output is correct
8 Correct 172 ms 153156 KB Output is correct
9 Correct 277 ms 153008 KB Output is correct
10 Correct 204 ms 153188 KB Output is correct
11 Correct 232 ms 153208 KB Output is correct
12 Correct 224 ms 145624 KB Output is correct
13 Correct 282 ms 146044 KB Output is correct
14 Correct 182 ms 150540 KB Output is correct
15 Correct 269 ms 155092 KB Output is correct
16 Correct 248 ms 154960 KB Output is correct
17 Correct 299 ms 152548 KB Output is correct
18 Correct 88 ms 133968 KB Output is correct
19 Correct 105 ms 134736 KB Output is correct
20 Correct 106 ms 134276 KB Output is correct
21 Correct 86 ms 133972 KB Output is correct
22 Correct 107 ms 134224 KB Output is correct
23 Correct 126 ms 133968 KB Output is correct
24 Runtime error 1448 ms 1048576 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -