oj.uz

Submission #515868

# Submission time Handle Problem Language Result Execution time Memory
515868 2022-01-20T04:20:26 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 175536 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 = 8000;
	
	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]];
			}
		}
	}
	
	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 36 ms 47200 KB Output is correct
3 Correct 36 ms 47308 KB Output is correct
4 Correct 37 ms 47296 KB Output is correct
5 Correct 33 ms 47308 KB Output is correct
6 Correct 34 ms 47180 KB Output is correct
7 Correct 36 ms 47208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 67412 KB Output is correct
2 Correct 159 ms 68032 KB Output is correct
3 Correct 464 ms 68088 KB Output is correct
4 Correct 470 ms 68300 KB Output is correct
5 Correct 348 ms 61028 KB Output is correct
6 Correct 328 ms 61216 KB Output is correct
7 Correct 137 ms 62580 KB Output is correct
8 Correct 253 ms 68364 KB Output is correct
9 Correct 235 ms 68240 KB Output is correct
10 Correct 385 ms 68308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 58496 KB Output is correct
2 Correct 269 ms 54784 KB Output is correct
3 Correct 244 ms 56680 KB Output is correct
4 Correct 739 ms 54732 KB Output is correct
5 Correct 245 ms 54320 KB Output is correct
6 Correct 107 ms 56424 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 36 ms 47200 KB Output is correct
3 Correct 36 ms 47308 KB Output is correct
4 Correct 37 ms 47296 KB Output is correct
5 Correct 33 ms 47308 KB Output is correct
6 Correct 34 ms 47180 KB Output is correct
7 Correct 36 ms 47208 KB Output is correct
8 Correct 102 ms 67412 KB Output is correct
9 Correct 159 ms 68032 KB Output is correct
10 Correct 464 ms 68088 KB Output is correct
11 Correct 470 ms 68300 KB Output is correct
12 Correct 348 ms 61028 KB Output is correct
13 Correct 328 ms 61216 KB Output is correct
14 Correct 137 ms 62580 KB Output is correct
15 Correct 253 ms 68364 KB Output is correct
16 Correct 235 ms 68240 KB Output is correct
17 Correct 385 ms 68308 KB Output is correct
18 Correct 73 ms 58496 KB Output is correct
19 Correct 269 ms 54784 KB Output is correct
20 Correct 244 ms 56680 KB Output is correct
21 Correct 739 ms 54732 KB Output is correct
22 Correct 245 ms 54320 KB Output is correct
23 Correct 107 ms 56424 KB Output is correct
24 Execution timed out 1575 ms 175536 KB Time limit exceeded
25 Halted 0 ms 0 KB -