Submission #108516

#	Time	Username	Problem	Language	Result	Execution time	Memory
108516		Diuven	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	342 ms	63312 KiB

selling_rna

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

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

inline int f(char c){
	switch (c)
	{
	case 'A': return 0;
	case 'G': return 1;
	case 'C': return 2;
	case 'U': return 3;
	default: return -1;
	}
}

class trie_t{
	struct node{
		int l=0, r=0;
		int nxt[4]={};
	};
	vector<node> T;
	int sz=0;
  public:
	trie_t(): T(1) { T.reserve(2000000); }
	void add(const string &S, int v=0, int i=0){
		if(i==int(S.size())) return;
		node &nd = T[v];
		int &link = nd.nxt[f(S[i])];
		if(link==0) link = T.size(), T.emplace_back();
		add(S, link, i+1);
	}

	void index(int v=0){
		T[v].l = ++sz, T[v].r = T[v].l;
		for(int k=0; k<4; k++){
			int x = T[v].nxt[k];
			if(x==0) continue;
			index(x); T[v].r = T[x].r;
		}
	}

	pii range(const string &S, int v=0, int i=0){
		node &nd = T[v];
		if(i==int(S.size())) return {nd.l, nd.r};
		int &link = nd.nxt[f(S[i])];
		if(link==0) return {-1, -1};
		return range(S, link, i+1);
	}

	void show(){
		cout<<"\nSHOWING!!\n";
		show(0);
		cout<<"Done!!\n";
	}
	void show(int v){
		cout<<"LINK of "<<v<<": ";
		for(int k=0; k<4; k++) cout<<T[v].nxt[k]<<' ';
		cout<<'\n';
		for(int k=0; k<4; k++){
			if(T[v].nxt[k]!=0) show(T[v].nxt[k]);
		}
		cout<<"Out from "<<v<<"\n";
	}
} Pref, Suff;

class Seg2_t{
	vector<int> X, Y;
	vector<pii> P;
	vector<int> root;
	struct node{
		int l, r, s;
	};
	vector<node> T;
	void compress(vector<int> &V){
		sort(V.begin(), V.end());
		V.resize(unique(V.begin(), V.end()) - V.begin());
	}
	int get(const vector<int> &V, int x){
		return upper_bound(V.begin(), V.end(), x) - V.begin();
	}
	int sum(int x, int y){
		x = get(X,x), y = get(Y,y);
		int ans = 0;
		// if(x<=0 || y<=0) return 0;
		// return sum(root[x], 1, Y.size(), y);
		if(x<=0 || y<=0) ans = 0;
		else ans = sum(root[x], 1, Y.size(), y);
		// cout<<"Sum of "<<x<<", "<<y<<": "<<ans<<'\n';
		return ans;
	}
	int sum(int v, int s, int e, int y){
		// cout<<"Sum Call: "<<v<<' '<<s<<' '<<e<<": "<<T[v].l<<", "<<T[v].r<<'\n';
		if(e<=y) return T[v].s;
		int mid = (s+e)/2, res = 0;
		if(T[v].l>0) res += sum(T[v].l, s, mid, y);
		if(mid<y && T[v].r>0) res += sum(T[v].r, mid+1, e, y);
		// cout<<"Sum: "<<v<<' '<<s<<' '<<e<<' '<<y<<": "<<res<<'\n';
		return res;
	}
	int make(int v, int s, int e, int p){
		T.push_back(T[v]); v = T.size()-1;
		T[v].s++;
		// cout<<"Make: "<<v<<' '<<s<<' '<<e<<' '<<p<<": "<<T[v].s<<endl;
		if(s==e){ return v; }
		int mid = (s+e)/2, tmp;
		if(p<=mid){
			// int tmp = make(T[v].l, s, mid, p);
			// T[v].l = tmp;
			// cout<<"WTF?: "<<tmp<<'\n';
			T[v].l = tmp = make(T[v].l, s, mid, p);
		}
		else{
			T[v].r = tmp = make(T[v].r, mid+1, e, p);
		}
		// cout<<"Out from "<<v<<": "<<T[v].l<<' '<<T[v].r<<endl;
		return v;
	}
  public:
	Seg2_t(): T(2){}
	void add(int x, int y){
		P.push_back({x,y});
		X.push_back(x), Y.push_back(y);
	}
	void init(){
		compress(X), compress(Y);
		root.resize(X.size()+1);
		sort(P.begin(), P.end());

		int now = 1;
		for(pii p:P){
			int x,y; tie(x,y) = p;
			x = get(X,x), y = get(Y,y);
			now = root[x] = make(now, 1, Y.size(), y);

			// for(int i=0; i<int(T.size()); i++){
			// 	node nd = T[i];
			// 	cout<<i<<": "<<nd.l<<' '<<nd.r<<": "<<nd.s<<endl;
			// }
			// cout<<endl;

			// cout<<"Doing "<<x<<"("<<root[x]<<") :";
			// for(int a=1; a<=int(Y.size()); a++)
			// 	cout<<sum(root[x], 1, Y.size(), a)<<' ';
			// cout<<'\n';
		}
	}
	int get_sum(int x1, int x2, int y1, int y2){
		return sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1);
	}
	void show(){
		return;
		cout<<"WTF?\n";
		for(pii p:P){
			int x,y; tie(x,y) = p;
			cout<<get(X,x)<<' '<<get(Y,y)<<'\n';
		}
		cout<<'\n';
	}
} Seg;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m; cin>>n>>m;

	static vector<string> S;
	
	for(int i=1; i<=n; i++){
		static string T; cin>>T;
		S.push_back(T);
		Pref.add(T);
		reverse(T.begin(), T.end());
		Suff.add(T);
	}

	Pref.index(); Suff.index();

	for(string &T : S){
		int x, y, z;
		tie(x,z) = Pref.range(T);
		reverse(T.begin(), T.end());
		tie(y,z) = Suff.range(T);
		reverse(T.begin(), T.end());

		Seg.add(x,y);
	}

	Seg.init();

	Seg.show();

	for(int i=1; i<=m; i++){
		static string P, Q; cin>>P>>Q;
		reverse(Q.begin(), Q.end());

		int x1,x2, y1,y2;
		tie(x1,x2) = Pref.range(P), tie(y1,y2) = Suff.range(Q);
		
		if(x1<0 || y1<0){ cout<<"0\n"; continue; }

		// cout<<x1<<' '<<x2<<", "<<y1<<' '<<y2<<'\n';

		cout<<Seg.get_sum(x1,x2,y1,y2)<<'\n';
	}

	return 0;
}

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