Submission #211347

#	Time	Username	Problem	Language	Result	Execution time	Memory
211347		quocnguyen1012	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	1604 ms	1048580 KiB

selling_rna

#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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40