oj.uz

Submission #515880

# Submission time Handle Problem Language Result Execution time Memory
515880 2022-01-20T04:48:29 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 203992 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, n + 1), ss(n, 0);
	vector<vector<map<int, int>>> 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++;
			int sum = s[last].size() - i;
			for(int j=last + 1;j<r[1];j++){
				if(pref[j][i] == pref[j-1][i]) { sum += s[j].size() - i; continue; }
				mm[pref[j-1][i]] = last; ss[last] = sum;
				tmp.push_back({last, j}); last = j; sum = s[j].size() - i;
			} if(last < r[1]){
				ss[last] = sum;
				mm[pref[r[1] - 1][i]] = last;
				tmp.push_back({last, r[1]});
			}
		} swap(seg, tmp);
		
		for(auto r : seg){
			if(ss[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(ss[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(auto r : seg){
			//~ if(r[1] - r[0] <= B) continue;
			
			//~ 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(int i=0;i<m;i++){
		cout<<res[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47216 KB Output is correct
2 Correct 45 ms 47304 KB Output is correct
3 Correct 35 ms 47308 KB Output is correct
4 Correct 36 ms 47296 KB Output is correct
5 Correct 36 ms 47240 KB Output is correct
6 Correct 36 ms 47216 KB Output is correct
7 Correct 35 ms 47308 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 58832 KB Output is correct
2 Correct 75 ms 55740 KB Output is correct
3 Correct 73 ms 56984 KB Output is correct
4 Correct 736 ms 54852 KB Output is correct
5 Correct 92 ms 54500 KB Output is correct
6 Correct 117 ms 56564 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47216 KB Output is correct
2 Correct 45 ms 47304 KB Output is correct
3 Correct 35 ms 47308 KB Output is correct
4 Correct 36 ms 47296 KB Output is correct
5 Correct 36 ms 47240 KB Output is correct
6 Correct 36 ms 47216 KB Output is correct
7 Correct 35 ms 47308 KB Output is correct
8 Execution timed out 1596 ms 203992 KB Time limit exceeded
9 Halted 0 ms 0 KB -