oj.uz

Submission #515900

# Submission time Handle Problem Language Result Execution time Memory
515900 2022-01-20T05:20:51 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 70600 KB 
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};

#define ar array
 
const int N = 2e6 + 5;
const int P = 167;
const int mod = (119 << 23) + 1;
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<string> s(n), r(n);
	vector<vector<int>> pref(n), suff(n);
	for(int i=0;i<n;i++){
		cin>>s[i]; 
	} sort(s.begin(), s.end());
	
	for(int i=0;i<n;i++){
		pref[i].resize(s[i].size());
		suff[i].resize(s[i].size());
		r[i] = s[i];
		reverse(r[i].begin(), r[i].end());
		for(int j=0;j<(int)s[i].size();j++){
			if(j) pref[i][j] = pref[i][j-1], suff[i][j] = suff[i][j-1];
			pref[i][j] = (pref[i][j] * 1ll * P + s[i][j]) % mod;
			suff[i][j] = (suff[i][j] * 1ll * P + r[i][j]) % mod;
		} 
	}
	
	vector<vector<ar<int, 4>>> qq(N);
	vector<int> res(m), tot;
	for(int i=0;i<m;i++){
		string p, q; cin>>p>>q; 
		reverse(q.begin(), q.end());
		int h1 = 0, h2 = 0;
		for(int j=0;j<(int)p.size();j++) h1 = (h1 * 1ll * P + p[j]) % mod;
		for(int j=0;j<(int)q.size();j++) h2 = (h2 * 1ll * P + q[j]) % mod;
		qq[(int)p.size() - 1].push_back({h1, (int)q.size() - 1, h2, i});
		tot.push_back((int)q.size() - 1);
	} sort(tot.begin(), tot.end());
	tot.erase(unique(tot.begin(), tot.end()), tot.end());
	
	vector<ar<int, 2>> seg; seg.push_back({0, n});
	vector<int> par(n);
	vector<vector<gp_hash_table<int, int, chash>>> pre(n);
	const int B = 10000;
	
	for(int i=0;i<N;i++){
		map<int, int> mm;
		vector<ar<int, 2>> tmp;
		
		for(auto r : seg){
			int last = r[0];
			while(last < r[1] && (int)s[last].size() == i) last++;
			for(int j=last + 1;j<r[1];j++){
				if(pref[j][i] == pref[j-1][i]) continue;
				mm[pref[j-1][i]] = last; 
				tmp.push_back({last, j}); last = j;
			} if(last < r[1]){
				mm[pref[r[1] - 1][i]] = last;
				tmp.push_back({last, r[1]});
			}
		} swap(seg, tmp);
		
		for(auto r : seg){
			if(r[1] - r[0] <= B) { par[r[0]] = r[1]; continue; }
			if(par[r[0]] == r[1]) continue;
			pre[r[0]].clear(); par[r[0]] = r[1];
			for(int j=r[0];j<r[1];j++){
				for(int i=0;i<(int)tot.size() && tot[i] < (int)s[j].size();i++){
					if((int)pre[r[0]].size() <= tot[i]) pre[r[0]].resize(tot[i] + 1);
					pre[r[0]][tot[i]][suff[j][tot[i]]]++;
				}
			} 
		}
		
		for(auto x : qq[i]){
			if(!mm.count(x[0])) continue;
			int l = mm[x[0]], r = par[l];
			if(r - l <= B){
				for(int j=l;j<r;j++){
					if((int)s[j].size() <= x[1]) continue;
					res[x[3]] += (suff[j][x[1]] == x[2]);
				} 
			} else {
				if((int)pre[l].size() > x[1]) res[x[3]] = pre[l][x[1]][x[2]];
			}
		}
	}
	
	for(int i=0;i<m;i++){
		cout<<res[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47308 KB Output is correct
2 Correct 39 ms 47308 KB Output is correct
3 Correct 32 ms 47308 KB Output is correct
4 Correct 33 ms 47256 KB Output is correct
5 Correct 37 ms 47284 KB Output is correct
6 Correct 33 ms 47284 KB Output is correct
7 Correct 37 ms 47300 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 67456 KB Output is correct
2 Correct 152 ms 68092 KB Output is correct
3 Correct 477 ms 67952 KB Output is correct
4 Correct 512 ms 68436 KB Output is correct
5 Correct 341 ms 61044 KB Output is correct
6 Correct 359 ms 61224 KB Output is correct
7 Correct 133 ms 62536 KB Output is correct
8 Correct 248 ms 68464 KB Output is correct
9 Correct 224 ms 68272 KB Output is correct
10 Correct 410 ms 68344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 58764 KB Output is correct
2 Correct 394 ms 54640 KB Output is correct
3 Correct 422 ms 56732 KB Output is correct
4 Correct 758 ms 54980 KB Output is correct
5 Correct 247 ms 54408 KB Output is correct
6 Correct 337 ms 56620 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47308 KB Output is correct
2 Correct 39 ms 47308 KB Output is correct
3 Correct 32 ms 47308 KB Output is correct
4 Correct 33 ms 47256 KB Output is correct
5 Correct 37 ms 47284 KB Output is correct
6 Correct 33 ms 47284 KB Output is correct
7 Correct 37 ms 47300 KB Output is correct
8 Correct 97 ms 67456 KB Output is correct
9 Correct 152 ms 68092 KB Output is correct
10 Correct 477 ms 67952 KB Output is correct
11 Correct 512 ms 68436 KB Output is correct
12 Correct 341 ms 61044 KB Output is correct
13 Correct 359 ms 61224 KB Output is correct
14 Correct 133 ms 62536 KB Output is correct
15 Correct 248 ms 68464 KB Output is correct
16 Correct 224 ms 68272 KB Output is correct
17 Correct 410 ms 68344 KB Output is correct
18 Correct 62 ms 58764 KB Output is correct
19 Correct 394 ms 54640 KB Output is correct
20 Correct 422 ms 56732 KB Output is correct
21 Correct 758 ms 54980 KB Output is correct
22 Correct 247 ms 54408 KB Output is correct
23 Correct 337 ms 56620 KB Output is correct
24 Correct 748 ms 69576 KB Output is correct
25 Execution timed out 1591 ms 70600 KB Time limit exceeded
26 Halted 0 ms 0 KB -