oj.uz

Submission #211347

# Submission time Handle Problem Language Result Execution time Memory
211347 2020-03-20T07:20:54 Z quocnguyen1012 Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 1048580 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5, base = 131;
const ll llinf = 1e18;

vector<ll> Hash[maxn];
vector<pair<ll, int>> need[maxn];
int N, M;
int res[maxn];
string p[maxn], q[maxn], str[maxn];
ll POW[maxn];
map<ll, vector<int>> pref;

ll get(int id, int l, int r)
{
  if(l == 0) return Hash[id][r];
  return Hash[id][r] - Hash[id][l - 1] * POW[r - l + 1];
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  POW[0] = 1;
  for(int i = 1; i < maxn; ++i)
    POW[i] = POW[i - 1] * base;
  cin >> N >> M;
  for(int i = 1; i <= N; ++i){
    cin >> str[i];
    Hash[i].assign(str[i].size(), 0);
    for(int j = 0; j < (int)str[i].size(); ++j){
      if(j) Hash[i][j] = Hash[i][j - 1] * base + str[i][j];
      else Hash[i][j] = str[i][j];
      pref[Hash[i][j]].pb(i);
    }
  }
  for(int i = 1; i <= M; ++i){
    cin >> p[i] >> q[i];
    ll hashp = 0;
    for(int j = 0; j < (int)p[i].size(); ++j){
      hashp = hashp * base + p[i][j];
    }
    ll hashq = 0;
    for(int j = 0; j < (int)q[i].size(); ++j){
      hashq = hashq * base + q[i][j];
    }
    for(auto & id : pref[hashp]) need[id].eb(hashq, i);
  }
  for(int i = 1; i <= N; ++i){
    for(auto id : need[i]){
      if(str[i].size() >= q[id.se].size()){
        if(get(i, str[i].size() - q[id.se].size(), str[i].size() - 1) == id.fi)
          res[id.se]++;
      }
    }
  }
  for(int i = 1; i <= M; ++i)
    cout << res[i] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30080 KB Output is correct
2 Correct 22 ms 30080 KB Output is correct
3 Correct 22 ms 30208 KB Output is correct
4 Correct 23 ms 30208 KB Output is correct
5 Correct 29 ms 30208 KB Output is correct
6 Correct 22 ms 30208 KB Output is correct
7 Correct 22 ms 30208 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 99816 KB Output is correct
2 Correct 558 ms 283256 KB Output is correct
3 Execution timed out 1604 ms 184952 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1188 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 30080 KB Output is correct
2 Correct 22 ms 30080 KB Output is correct
3 Correct 22 ms 30208 KB Output is correct
4 Correct 23 ms 30208 KB Output is correct
5 Correct 29 ms 30208 KB Output is correct
6 Correct 22 ms 30208 KB Output is correct
7 Correct 22 ms 30208 KB Output is correct
8 Correct 335 ms 99816 KB Output is correct
9 Correct 558 ms 283256 KB Output is correct
10 Execution timed out 1604 ms 184952 KB Time limit exceeded
11 Halted 0 ms 0 KB -