oj.uz

Submission #515898

# Submission time Handle Problem Language Result Execution time Memory
515898 2022-01-20T05:15:10 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 70568 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 {
				if((int)pre[l].size() > x[1]) 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 47280 KB Output is correct
2 Correct 33 ms 47196 KB Output is correct
3 Correct 34 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 34 ms 47308 KB Output is correct
6 Correct 33 ms 47292 KB Output is correct
7 Correct 33 ms 47252 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 67476 KB Output is correct
2 Correct 152 ms 68056 KB Output is correct
3 Correct 457 ms 67964 KB Output is correct
4 Correct 491 ms 68320 KB Output is correct
5 Correct 325 ms 60984 KB Output is correct
6 Correct 346 ms 61356 KB Output is correct
7 Correct 127 ms 62532 KB Output is correct
8 Correct 240 ms 68452 KB Output is correct
9 Correct 234 ms 68356 KB Output is correct
10 Correct 381 ms 68296 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 58756 KB Output is correct
2 Correct 424 ms 54644 KB Output is correct
3 Correct 431 ms 56732 KB Output is correct
4 Correct 738 ms 54992 KB Output is correct
5 Correct 254 ms 54412 KB Output is correct
6 Correct 342 ms 56620 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47280 KB Output is correct
2 Correct 33 ms 47196 KB Output is correct
3 Correct 34 ms 47308 KB Output is correct
4 Correct 33 ms 47308 KB Output is correct
5 Correct 34 ms 47308 KB Output is correct
6 Correct 33 ms 47292 KB Output is correct
7 Correct 33 ms 47252 KB Output is correct
8 Correct 99 ms 67476 KB Output is correct
9 Correct 152 ms 68056 KB Output is correct
10 Correct 457 ms 67964 KB Output is correct
11 Correct 491 ms 68320 KB Output is correct
12 Correct 325 ms 60984 KB Output is correct
13 Correct 346 ms 61356 KB Output is correct
14 Correct 127 ms 62532 KB Output is correct
15 Correct 240 ms 68452 KB Output is correct
16 Correct 234 ms 68356 KB Output is correct
17 Correct 381 ms 68296 KB Output is correct
18 Correct 65 ms 58756 KB Output is correct
19 Correct 424 ms 54644 KB Output is correct
20 Correct 431 ms 56732 KB Output is correct
21 Correct 738 ms 54992 KB Output is correct
22 Correct 254 ms 54412 KB Output is correct
23 Correct 342 ms 56620 KB Output is correct
24 Correct 774 ms 69568 KB Output is correct
25 Execution timed out 1578 ms 70568 KB Time limit exceeded
26 Halted 0 ms 0 KB -