Submission #515907

#	Time	Username	Problem	Language	Result	Execution time	Memory
515907		amunduzbaev	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	212 ms	206040 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;

#define ar array
 
const int N = 2e6 + 5;

struct TRIE{
	int tree[N][4];
	int last, tin[N], tout[N], t;
	
	int get(char c){
		if(c == 'A') return 0;
		if(c == 'G') return 1;
		if(c == 'C') return 2;
		return 3;
	}

	int add(string& s){
		int cur = 0;
		for(int i=0;i<(int)s.size();i++){
			int x = get(s[i]);
			if(tree[cur][x]) cur = tree[cur][x];
			else tree[cur][x] = ++last, cur = last;
		} return cur;
	}
	
	void dfs(int u = 0){
		tin[u] = ++t;
		for(int k=0;k<4;k++){
			if(tree[u][k]) dfs(tree[u][k]);
		} tout[u] = t;
	}
}tree;

struct BIT{
	int tree[N];
	
	void add(int i, int v){
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){
		int rr = 0;
		for(;i>0;i-=(i&-i)) rr += tree[i];
		return rr;
	}
	
	int get(int l, int r){
		return get(r) - get(l-1);
	}
}bit;

vector<int> in[N], out[N], pp[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<string> s(n), r(n), p(m), q(m);
	for(int i=0;i<n;i++){
		cin>>s[i];
		r[i] = s[i];
		reverse(r[i].begin(), r[i].end());
	}
	
	for(int i=0;i<m;i++){
		cin>>p[i]>>q[i];
		reverse(q[i].begin(), q[i].end());
	}
	
	vector<ar<int, 2>> t(n);
	vector<ar<int, 2>> a(m), b(m);
	
	{
		tree.last = tree.t = 0;
		vector<int> v(n), u(m);
		for(int i=0;i<n;i++) v[i] = tree.add(s[i]);
		for(int i=0;i<m;i++) u[i] = tree.add(p[i]);
		
		tree.dfs();
		for(int i=0;i<n;i++){
			t[i][0] = tree.tin[v[i]];
		}
		
		for(int i=0;i<m;i++){
			a[i][0] = tree.tin[u[i]];
			a[i][1] = tree.tout[u[i]];
		}
		
		memset(tree.tree, 0, sizeof tree.tree);
	}
	
	{
		tree.last = tree.t = 0;
		vector<int> v(n), u(m);
		for(int i=0;i<n;i++) v[i] = tree.add(r[i]);
		for(int i=0;i<m;i++) u[i] = tree.add(q[i]);
		
		tree.dfs();
		for(int i=0;i<n;i++){
			t[i][1] = tree.tin[v[i]];
		}
		
		for(int i=0;i<m;i++){
			b[i][0] = tree.tin[u[i]];
			b[i][1] = tree.tout[u[i]];
		}
		
		memset(tree.tree, 0, sizeof tree.tree);
	}
	
	//~ for(int i=0;i<n;i++) cout<<t[i][0]<<" "<<t[i][1]<<"\n";
	//~ for(int i=0;i<m;i++){
		//~ cout<<a[i][0]<<" "<<a[i][1]<<" \n"<<b[i][0]<<" "<<b[i][1]<<"\n\n";
	//~ }
	
	vector<int> res(m);
	for(int i=0;i<m;i++){
		in[a[i][0]].push_back(i);
		out[a[i][1]].push_back(i);
	} for(int i=0;i<n;i++){
		pp[t[i][0]].push_back(t[i][1]);
	}
	
	for(int i=0;i<N;i++){
		for(auto j : in[i]){
			res[j] -= bit.get(b[j][0], b[j][1]);
		}
		
		for(auto j : pp[i]){
			bit.add(j, 1);
		}
		
		for(auto j : out[i]){
			res[j] += bit.get(b[j][0], b[j][1]);
		}
	}
	
	for(int i=0;i<m;i++){
		cout<<res[i]<<"\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40