Submission #108477

#	Time	Username	Problem	Language	Result	Execution time	Memory
108477		Diuven	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	45 ms	6636 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) {}
	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);
		if(x<=0 || y<=0) return 0;
		return sum(root[x], 1, Y.size(), y);
	}
	int sum(int v, int s, int e, int y){
		node &nd = T[v];
		if(e<=y) return nd.s;
		if(y<s)  return 0;
		int mid = (s+e)/2;
		return sum(nd.l, s, mid, y) + sum(nd.r, mid+1, e, y);
	}
	int make(int v, int s, int e, int p){
		T.push_back(T[v]); v = T.size()-1;
		node &nd = T[v]; nd.s++;
		if(s==e){ return v;}
		int mid = (s+e)/2;
		if(p<=mid) nd.l = make(nd.l, s, mid, p);
		else       nd.r = make(nd.r, mid+1, e, p);
		return v;
	}
  public:
	Seg2_t(): T(1){}
	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 = 0;
		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);
		}
	}
	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);
	}
} Seg;

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

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

	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();

	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<<Seg.get_sum(x1,x2,y1,y2)<<'\n';
	}

	return 0;
}

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