oj.uz

Submission #515870

# Submission time Handle Problem Language Result Execution time Memory
515870 2022-01-20T04:21:24 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 68404 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 = 20000;
	
	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 47296 KB Output is correct
2 Correct 34 ms 47268 KB Output is correct
3 Correct 37 ms 47304 KB Output is correct
4 Correct 41 ms 47308 KB Output is correct
5 Correct 35 ms 47308 KB Output is correct
6 Correct 33 ms 47308 KB Output is correct
7 Correct 33 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 67400 KB Output is correct
2 Correct 201 ms 68080 KB Output is correct
3 Correct 477 ms 68064 KB Output is correct
4 Correct 467 ms 68192 KB Output is correct
5 Correct 337 ms 61044 KB Output is correct
6 Correct 351 ms 61196 KB Output is correct
7 Correct 152 ms 62532 KB Output is correct
8 Correct 241 ms 68404 KB Output is correct
9 Correct 228 ms 68268 KB Output is correct
10 Correct 372 ms 68288 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 58500 KB Output is correct
2 Correct 984 ms 54464 KB Output is correct
3 Execution timed out 1505 ms 56684 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47296 KB Output is correct
2 Correct 34 ms 47268 KB Output is correct
3 Correct 37 ms 47304 KB Output is correct
4 Correct 41 ms 47308 KB Output is correct
5 Correct 35 ms 47308 KB Output is correct
6 Correct 33 ms 47308 KB Output is correct
7 Correct 33 ms 47308 KB Output is correct
8 Correct 95 ms 67400 KB Output is correct
9 Correct 201 ms 68080 KB Output is correct
10 Correct 477 ms 68064 KB Output is correct
11 Correct 467 ms 68192 KB Output is correct
12 Correct 337 ms 61044 KB Output is correct
13 Correct 351 ms 61196 KB Output is correct
14 Correct 152 ms 62532 KB Output is correct
15 Correct 241 ms 68404 KB Output is correct
16 Correct 228 ms 68268 KB Output is correct
17 Correct 372 ms 68288 KB Output is correct
18 Correct 1069 ms 58500 KB Output is correct
19 Correct 984 ms 54464 KB Output is correct
20 Execution timed out 1505 ms 56684 KB Time limit exceeded
21 Halted 0 ms 0 KB -