oj.uz

Submission #515878

# Submission time Handle Problem Language Result Execution time Memory
515878 2022-01-20T04:38:58 Z amunduzbaev Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 68332 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, n + 1);
	vector<vector<map<int, int>>> pre(n);
	const int B = 100000;
	
	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]];
				//~ q[l].push_back({x[1], x[2], x[3]});
			}
		}
		
		//~ for(auto r : seg){
			//~ if(r[1] - r[0] <= B) continue;
			
			//~ 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(int i=0;i<m;i++){
		cout<<res[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47308 KB Output is correct
2 Correct 34 ms 47308 KB Output is correct
3 Correct 37 ms 47308 KB Output is correct
4 Correct 35 ms 47308 KB Output is correct
5 Correct 34 ms 47308 KB Output is correct
6 Correct 34 ms 47308 KB Output is correct
7 Correct 35 ms 47200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 67444 KB Output is correct
2 Correct 150 ms 67984 KB Output is correct
3 Correct 482 ms 67960 KB Output is correct
4 Correct 501 ms 68296 KB Output is correct
5 Correct 342 ms 61032 KB Output is correct
6 Correct 331 ms 61180 KB Output is correct
7 Correct 132 ms 62664 KB Output is correct
8 Correct 233 ms 68332 KB Output is correct
9 Correct 219 ms 68268 KB Output is correct
10 Correct 374 ms 68292 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 58252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47308 KB Output is correct
2 Correct 34 ms 47308 KB Output is correct
3 Correct 37 ms 47308 KB Output is correct
4 Correct 35 ms 47308 KB Output is correct
5 Correct 34 ms 47308 KB Output is correct
6 Correct 34 ms 47308 KB Output is correct
7 Correct 35 ms 47200 KB Output is correct
8 Correct 105 ms 67444 KB Output is correct
9 Correct 150 ms 67984 KB Output is correct
10 Correct 482 ms 67960 KB Output is correct
11 Correct 501 ms 68296 KB Output is correct
12 Correct 342 ms 61032 KB Output is correct
13 Correct 331 ms 61180 KB Output is correct
14 Correct 132 ms 62664 KB Output is correct
15 Correct 233 ms 68332 KB Output is correct
16 Correct 219 ms 68268 KB Output is correct
17 Correct 374 ms 68292 KB Output is correct
18 Execution timed out 1589 ms 58252 KB Time limit exceeded
19 Halted 0 ms 0 KB -