oj.uz

Submission #515891

# Submission time Handle Problem Language Result Execution time Memory
515891 2022-01-20T05:01:25 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 71188 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){
			par[r[0]] = r[1];
			if(r[1] - r[0] <= B) continue;
			pre[r[0]].clear();
			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 33 ms 47268 KB Output is correct
2 Correct 32 ms 47308 KB Output is correct
3 Correct 32 ms 47280 KB Output is correct
4 Correct 34 ms 47276 KB Output is correct
5 Correct 41 ms 47200 KB Output is correct
6 Correct 41 ms 47268 KB Output is correct
7 Correct 33 ms 47312 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 68096 KB Output is correct
2 Correct 201 ms 68732 KB Output is correct
3 Correct 477 ms 68544 KB Output is correct
4 Correct 513 ms 68892 KB Output is correct
5 Correct 381 ms 61612 KB Output is correct
6 Correct 365 ms 61876 KB Output is correct
7 Correct 158 ms 63220 KB Output is correct
8 Correct 248 ms 69052 KB Output is correct
9 Correct 266 ms 69036 KB Output is correct
10 Correct 494 ms 68928 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 59208 KB Output is correct
2 Correct 415 ms 54992 KB Output is correct
3 Correct 417 ms 57120 KB Output is correct
4 Correct 793 ms 55372 KB Output is correct
5 Correct 281 ms 54744 KB Output is correct
6 Correct 382 ms 57104 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47268 KB Output is correct
2 Correct 32 ms 47308 KB Output is correct
3 Correct 32 ms 47280 KB Output is correct
4 Correct 34 ms 47276 KB Output is correct
5 Correct 41 ms 47200 KB Output is correct
6 Correct 41 ms 47268 KB Output is correct
7 Correct 33 ms 47312 KB Output is correct
8 Correct 115 ms 68096 KB Output is correct
9 Correct 201 ms 68732 KB Output is correct
10 Correct 477 ms 68544 KB Output is correct
11 Correct 513 ms 68892 KB Output is correct
12 Correct 381 ms 61612 KB Output is correct
13 Correct 365 ms 61876 KB Output is correct
14 Correct 158 ms 63220 KB Output is correct
15 Correct 248 ms 69052 KB Output is correct
16 Correct 266 ms 69036 KB Output is correct
17 Correct 494 ms 68928 KB Output is correct
18 Correct 71 ms 59208 KB Output is correct
19 Correct 415 ms 54992 KB Output is correct
20 Correct 417 ms 57120 KB Output is correct
21 Correct 793 ms 55372 KB Output is correct
22 Correct 281 ms 54744 KB Output is correct
23 Correct 382 ms 57104 KB Output is correct
24 Correct 747 ms 70208 KB Output is correct
25 Execution timed out 1551 ms 71188 KB Time limit exceeded
26 Halted 0 ms 0 KB -