oj.uz

Submission #515875

# Submission time Handle Problem Language Result Execution time Memory
515875 2022-01-20T04:33:18 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 70296 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<unordered_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 34 ms 47276 KB Output is correct
2 Correct 33 ms 47308 KB Output is correct
3 Correct 34 ms 47192 KB Output is correct
4 Correct 34 ms 47308 KB Output is correct
5 Correct 35 ms 47264 KB Output is correct
6 Correct 38 ms 47200 KB Output is correct
7 Correct 34 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 67532 KB Output is correct
2 Correct 157 ms 68088 KB Output is correct
3 Correct 446 ms 67956 KB Output is correct
4 Correct 461 ms 68336 KB Output is correct
5 Correct 315 ms 61008 KB Output is correct
6 Correct 321 ms 61216 KB Output is correct
7 Correct 133 ms 62548 KB Output is correct
8 Correct 237 ms 68400 KB Output is correct
9 Correct 223 ms 68212 KB Output is correct
10 Correct 371 ms 68288 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 58476 KB Output is correct
2 Correct 395 ms 54536 KB Output is correct
3 Correct 410 ms 56624 KB Output is correct
4 Correct 718 ms 54740 KB Output is correct
5 Correct 269 ms 54332 KB Output is correct
6 Correct 334 ms 56396 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47276 KB Output is correct
2 Correct 33 ms 47308 KB Output is correct
3 Correct 34 ms 47192 KB Output is correct
4 Correct 34 ms 47308 KB Output is correct
5 Correct 35 ms 47264 KB Output is correct
6 Correct 38 ms 47200 KB Output is correct
7 Correct 34 ms 47308 KB Output is correct
8 Correct 102 ms 67532 KB Output is correct
9 Correct 157 ms 68088 KB Output is correct
10 Correct 446 ms 67956 KB Output is correct
11 Correct 461 ms 68336 KB Output is correct
12 Correct 315 ms 61008 KB Output is correct
13 Correct 321 ms 61216 KB Output is correct
14 Correct 133 ms 62548 KB Output is correct
15 Correct 237 ms 68400 KB Output is correct
16 Correct 223 ms 68212 KB Output is correct
17 Correct 371 ms 68288 KB Output is correct
18 Correct 64 ms 58476 KB Output is correct
19 Correct 395 ms 54536 KB Output is correct
20 Correct 410 ms 56624 KB Output is correct
21 Correct 718 ms 54740 KB Output is correct
22 Correct 269 ms 54332 KB Output is correct
23 Correct 334 ms 56396 KB Output is correct
24 Correct 757 ms 69444 KB Output is correct
25 Execution timed out 1589 ms 70296 KB Time limit exceeded
26 Halted 0 ms 0 KB -