oj.uz

Submission #515886

# Submission time Handle Problem Language Result Execution time Memory
515886 2022-01-20T04:53:53 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 469 ms 68040 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());
	map<int, int> mm;
	for(int i=0;i<(int)tot.size();i++) mm[tot[i]] = i;
	for(int i=0;i<N;i++){
		for(auto& x : qq[i]){
			x[1] = mm[x[1]];
		}
	}
	
	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;
			par[r[0]] = r[1];
			pre[r[0]].resize(tot.size());
			for(int j=r[0];j<r[1];j++){
				int in = -1;
				for(auto l : tot){ in++;
					if(l >= (int)s[j].size()) break;
					pre[r[0]][in][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 41 ms 47236 KB Output is correct
2 Correct 39 ms 47308 KB Output is correct
3 Correct 51 ms 47308 KB Output is correct
4 Correct 49 ms 47180 KB Output is correct
5 Correct 46 ms 47208 KB Output is correct
6 Correct 40 ms 47192 KB Output is correct
7 Correct 41 ms 47308 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 67452 KB Output is correct
2 Correct 182 ms 68040 KB Output is correct
3 Incorrect 469 ms 68012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 58756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47236 KB Output is correct
2 Correct 39 ms 47308 KB Output is correct
3 Correct 51 ms 47308 KB Output is correct
4 Correct 49 ms 47180 KB Output is correct
5 Correct 46 ms 47208 KB Output is correct
6 Correct 40 ms 47192 KB Output is correct
7 Correct 41 ms 47308 KB Output is correct
8 Correct 128 ms 67452 KB Output is correct
9 Correct 182 ms 68040 KB Output is correct
10 Incorrect 469 ms 68012 KB Output isn't correct
11 Halted 0 ms 0 KB -