oj.uz

Submission #108516

# Submission time Handle Problem Language Result Execution time Memory
108516 2019-04-30T06:17:00 Z Diuven Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 342 ms 63312 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 53164 KB Output is correct
2 Correct 152 ms 51424 KB Output is correct
3 Correct 161 ms 52924 KB Output is correct
4 Correct 147 ms 50988 KB Output is correct
5 Correct 201 ms 62436 KB Output is correct
6 Correct 197 ms 63312 KB Output is correct
7 Correct 57 ms 8084 KB Output is correct
8 Correct 159 ms 43084 KB Output is correct
9 Correct 142 ms 37536 KB Output is correct
10 Correct 102 ms 34308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6252 KB Output is correct
2 Correct 45 ms 8944 KB Output is correct
3 Correct 62 ms 10224 KB Output is correct
4 Correct 29 ms 5336 KB Output is correct
5 Correct 44 ms 8804 KB Output is correct
6 Correct 53 ms 10348 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 153 ms 53164 KB Output is correct
9 Correct 152 ms 51424 KB Output is correct
10 Correct 161 ms 52924 KB Output is correct
11 Correct 147 ms 50988 KB Output is correct
12 Correct 201 ms 62436 KB Output is correct
13 Correct 197 ms 63312 KB Output is correct
14 Correct 57 ms 8084 KB Output is correct
15 Correct 159 ms 43084 KB Output is correct
16 Correct 142 ms 37536 KB Output is correct
17 Correct 102 ms 34308 KB Output is correct
18 Correct 34 ms 6252 KB Output is correct
19 Correct 45 ms 8944 KB Output is correct
20 Correct 62 ms 10224 KB Output is correct
21 Correct 29 ms 5336 KB Output is correct
22 Correct 44 ms 8804 KB Output is correct
23 Correct 53 ms 10348 KB Output is correct
24 Correct 185 ms 46784 KB Output is correct
25 Correct 217 ms 47140 KB Output is correct
26 Correct 173 ms 46296 KB Output is correct
27 Correct 164 ms 46328 KB Output is correct
28 Correct 342 ms 42788 KB Output is correct
29 Correct 157 ms 22116 KB Output is correct