oj.uz

Submission #972167

# Submission time Handle Problem Language Result Execution time Memory
972167 2024-04-30T08:02:45 Z duckindog Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 269 ms 22100 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5'000 + 10,
          base = 19937;
int n, m;

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

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

  cin >> n >> m;

  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";
  }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 20248 KB Output is correct
2 Correct 260 ms 20300 KB Output is correct
3 Correct 132 ms 20256 KB Output is correct
4 Correct 160 ms 20304 KB Output is correct
5 Correct 150 ms 12884 KB Output is correct
6 Correct 166 ms 13056 KB Output is correct
7 Correct 168 ms 17744 KB Output is correct
8 Correct 199 ms 22100 KB Output is correct
9 Correct 191 ms 22084 KB Output is correct
10 Correct 269 ms 19752 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 80 ms 20248 KB Output is correct
9 Correct 260 ms 20300 KB Output is correct
10 Correct 132 ms 20256 KB Output is correct
11 Correct 160 ms 20304 KB Output is correct
12 Correct 150 ms 12884 KB Output is correct
13 Correct 166 ms 13056 KB Output is correct
14 Correct 168 ms 17744 KB Output is correct
15 Correct 199 ms 22100 KB Output is correct
16 Correct 191 ms 22084 KB Output is correct
17 Correct 269 ms 19752 KB Output is correct
18 Runtime error 2 ms 1116 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -