oj.uz

Submission #515874

# Submission time Handle Problem Language Result Execution time Memory
515874 2022-01-20T04:32:11 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 70272 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);
	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++;
			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;
			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]];
				//~ q[l].push_back({});
			}
		}
		
		//~ for(auto r : seg){
			//~ if(r[1] - r[0] <= B) continue;
			//~ for(auto x : q[r[0]]){
				
				//~ }
		//~ }
	}
	
	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 33 ms 47308 KB Output is correct
2 Correct 35 ms 47308 KB Output is correct
3 Correct 37 ms 47260 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 33 ms 47308 KB Output is correct
6 Correct 33 ms 47304 KB Output is correct
7 Correct 38 ms 47196 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 67348 KB Output is correct
2 Correct 157 ms 68064 KB Output is correct
3 Correct 448 ms 68092 KB Output is correct
4 Correct 458 ms 68300 KB Output is correct
5 Correct 333 ms 60996 KB Output is correct
6 Correct 341 ms 61192 KB Output is correct
7 Correct 128 ms 62568 KB Output is correct
8 Correct 237 ms 68452 KB Output is correct
9 Correct 228 ms 68212 KB Output is correct
10 Correct 381 ms 68272 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 58424 KB Output is correct
2 Correct 401 ms 54628 KB Output is correct
3 Correct 413 ms 56788 KB Output is correct
4 Correct 710 ms 54724 KB Output is correct
5 Correct 254 ms 54320 KB Output is correct
6 Correct 351 ms 56388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47308 KB Output is correct
2 Correct 35 ms 47308 KB Output is correct
3 Correct 37 ms 47260 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 33 ms 47308 KB Output is correct
6 Correct 33 ms 47304 KB Output is correct
7 Correct 38 ms 47196 KB Output is correct
8 Correct 94 ms 67348 KB Output is correct
9 Correct 157 ms 68064 KB Output is correct
10 Correct 448 ms 68092 KB Output is correct
11 Correct 458 ms 68300 KB Output is correct
12 Correct 333 ms 60996 KB Output is correct
13 Correct 341 ms 61192 KB Output is correct
14 Correct 128 ms 62568 KB Output is correct
15 Correct 237 ms 68452 KB Output is correct
16 Correct 228 ms 68212 KB Output is correct
17 Correct 381 ms 68272 KB Output is correct
18 Correct 64 ms 58424 KB Output is correct
19 Correct 401 ms 54628 KB Output is correct
20 Correct 413 ms 56788 KB Output is correct
21 Correct 710 ms 54724 KB Output is correct
22 Correct 254 ms 54320 KB Output is correct
23 Correct 351 ms 56388 KB Output is correct
24 Correct 754 ms 69472 KB Output is correct
25 Execution timed out 1598 ms 70272 KB Time limit exceeded
26 Halted 0 ms 0 KB -