oj.uz

Submission #515892

# Submission time Handle Problem Language Result Execution time Memory
515892 2022-01-20T05:03:06 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 70588 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), 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<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;
			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 {
				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 37 ms 47276 KB Output is correct
2 Correct 44 ms 47180 KB Output is correct
3 Correct 44 ms 47292 KB Output is correct
4 Correct 44 ms 47228 KB Output is correct
5 Correct 43 ms 47308 KB Output is correct
6 Correct 45 ms 47308 KB Output is correct
7 Correct 35 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 67396 KB Output is correct
2 Correct 159 ms 68136 KB Output is correct
3 Correct 488 ms 67944 KB Output is correct
4 Correct 487 ms 68320 KB Output is correct
5 Correct 370 ms 61052 KB Output is correct
6 Correct 396 ms 61248 KB Output is correct
7 Correct 153 ms 62528 KB Output is correct
8 Correct 245 ms 68376 KB Output is correct
9 Correct 238 ms 68388 KB Output is correct
10 Correct 377 ms 68328 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 58680 KB Output is correct
2 Correct 440 ms 54636 KB Output is correct
3 Correct 450 ms 56728 KB Output is correct
4 Correct 762 ms 54980 KB Output is correct
5 Correct 275 ms 54364 KB Output is correct
6 Correct 350 ms 56668 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47276 KB Output is correct
2 Correct 44 ms 47180 KB Output is correct
3 Correct 44 ms 47292 KB Output is correct
4 Correct 44 ms 47228 KB Output is correct
5 Correct 43 ms 47308 KB Output is correct
6 Correct 45 ms 47308 KB Output is correct
7 Correct 35 ms 47308 KB Output is correct
8 Correct 96 ms 67396 KB Output is correct
9 Correct 159 ms 68136 KB Output is correct
10 Correct 488 ms 67944 KB Output is correct
11 Correct 487 ms 68320 KB Output is correct
12 Correct 370 ms 61052 KB Output is correct
13 Correct 396 ms 61248 KB Output is correct
14 Correct 153 ms 62528 KB Output is correct
15 Correct 245 ms 68376 KB Output is correct
16 Correct 238 ms 68388 KB Output is correct
17 Correct 377 ms 68328 KB Output is correct
18 Correct 69 ms 58680 KB Output is correct
19 Correct 440 ms 54636 KB Output is correct
20 Correct 450 ms 56728 KB Output is correct
21 Correct 762 ms 54980 KB Output is correct
22 Correct 275 ms 54364 KB Output is correct
23 Correct 350 ms 56668 KB Output is correct
24 Correct 692 ms 69576 KB Output is correct
25 Execution timed out 1601 ms 70588 KB Time limit exceeded
26 Halted 0 ms 0 KB -