oj.uz

Submission #515861

# Submission time Handle Problem Language Result Execution time Memory
515861 2022-01-20T04:12:12 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 216244 KB 
#include "bits/stdc++.h"
using namespace std;

#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);
	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});
	}
	vector<ar<int, 2>> seg; seg.push_back({0, n});
	vector<int> par(n);
	vector<vector<map<int, int>>> pre(n);
	const int B = 1;
	
	for(int i=0;i<10;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 x : seg) cout<<x[0]<<" "<<x[1]<<"\n";
		//~ cout<<"\n";
		
		for(auto r : seg){
			if(r[1] - r[0] <= B) { par[r[0]] = r[1]; continue; }
			if(par[r[0]] == r[1]) continue;
			par[r[0]] = r[1];
			pre[r[0]].clear();
			for(int j=r[0];j<r[1];j++){
				if(pre[r[0]].size() < s[j].size()) pre[r[0]].resize(s[j].size());
				for(int l=0;l<(int)s[j].size();l++){
					pre[r[0]][l][suff[j][l]]++;
				}
			}
		}
		
		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 {
				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 22 ms 47308 KB Output is correct
2 Correct 21 ms 47284 KB Output is correct
3 Correct 21 ms 47332 KB Output is correct
4 Correct 25 ms 47308 KB Output is correct
5 Correct 21 ms 47232 KB Output is correct
6 Correct 21 ms 47332 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1610 ms 216244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 58876 KB Output is correct
2 Correct 59 ms 56892 KB Output is correct
3 Correct 60 ms 58048 KB Output is correct
4 Correct 43 ms 55140 KB Output is correct
5 Correct 47 ms 55772 KB Output is correct
6 Correct 53 ms 57504 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47308 KB Output is correct
2 Correct 21 ms 47284 KB Output is correct
3 Correct 21 ms 47332 KB Output is correct
4 Correct 25 ms 47308 KB Output is correct
5 Correct 21 ms 47232 KB Output is correct
6 Correct 21 ms 47332 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct
8 Execution timed out 1610 ms 216244 KB Time limit exceeded
9 Halted 0 ms 0 KB -