oj.uz

Submission #535910

# Submission time Handle Problem Language Result Execution time Memory
535910 2022-03-11T19:29:23 Z michao Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 363 ms 169784 KB 
#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=1e5+5;
const int MAXT=2e6+5;
const int inf=(int)1e9+9;
string S[MAXN];
string P[MAXN];
string Q[MAXN];
int syn[MAXT][4];
int mini[MAXT];
int maxi[MAXT];
vi ids[MAXT];
int f(char x){
	if (x=='A')return 0;
	if (x=='G')return 1;
	if (x=='C')return 2;
	return 3;
}

int cnt=0;
pii przedzial[MAXN];

void update(int u,int x){
	mini[u]=min(mini[u],x);
	maxi[u]=max(maxi[u],x);
}	

void wstaw1(string s,int id){
	int u=0;
	update(u,id);
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])syn[u][to]=++cnt;
		u=syn[u][to];
		update(u,id);
	}
}

void wstaw2(string s,int id){
	int u=0;
	ids[u].pb(id);
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])syn[u][to]=++cnt;
		u=syn[u][to];
		ids[u].pb(id);
	}
}
pii search1(string s){
	int u=0;
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])return mp(inf,-inf);
		u=syn[u][to];
	}
	return mp(mini[u],maxi[u]);
}

vi search2(string s){
	int u=0;
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])return {};
		u=syn[u][to];
	}
	return ids[u];
}

int func(vi &v,int l,int r){
	if (l>r)return 0;
	if (v.empty())return 0;
	if (r<v[0] || l>v.back())return 0;
	auto itl=lower_bound(v.begin(),v.end(),l)-v.begin();
	auto itr=(--upper_bound(v.begin(),v.end(),r))-v.begin();
	return (int)itr-(int)itl+1;
}
int32_t main(){
  BOOST;
  fill(mini,mini+MAXT,inf);
  fill(maxi,maxi+MAXT,-inf);
  int n,m;
  cin>>n>>m;
  for (int i=1;i<=n;i++)cin>>S[i];
  sort(S+1,S+n+1);
  for (int i=1;i<=n;i++)wstaw1(S[i],i);
  for (int i=1;i<=m;i++){
		cin>>P[i]>>Q[i];
		przedzial[i]=search1(P[i]);
	}
	for (int i=0;i<MAXT;i++)for (int j=0;j<4;j++)syn[i][j]=0;
	cnt=0;
	for (int i=1;i<=n;i++){
		reverse(S[i].begin(),S[i].end());
		wstaw2(S[i],i);
	}
	for (int i=1;i<=m;i++){
		reverse(Q[i].begin(),Q[i].end());
		vi v=search2(Q[i]);
		cout<<func(v,przedzial[i].st,przedzial[i].nd)<<"\n";
	}
  return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 103628 KB Output is correct
2 Correct 51 ms 103596 KB Output is correct
3 Correct 52 ms 103520 KB Output is correct
4 Correct 64 ms 103568 KB Output is correct
5 Correct 57 ms 103628 KB Output is correct
6 Correct 53 ms 103628 KB Output is correct
7 Correct 52 ms 103556 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 169784 KB Output is correct
2 Correct 202 ms 166704 KB Output is correct
3 Correct 123 ms 119560 KB Output is correct
4 Correct 129 ms 119060 KB Output is correct
5 Correct 148 ms 144704 KB Output is correct
6 Correct 170 ms 147664 KB Output is correct
7 Correct 113 ms 123204 KB Output is correct
8 Correct 178 ms 143988 KB Output is correct
9 Correct 161 ms 140032 KB Output is correct
10 Correct 148 ms 134456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 105224 KB Output is correct
2 Correct 80 ms 104780 KB Output is correct
3 Correct 104 ms 104840 KB Output is correct
4 Correct 99 ms 104700 KB Output is correct
5 Correct 111 ms 104736 KB Output is correct
6 Correct 131 ms 104960 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 103628 KB Output is correct
2 Correct 51 ms 103596 KB Output is correct
3 Correct 52 ms 103520 KB Output is correct
4 Correct 64 ms 103568 KB Output is correct
5 Correct 57 ms 103628 KB Output is correct
6 Correct 53 ms 103628 KB Output is correct
7 Correct 52 ms 103556 KB Output is correct
8 Correct 199 ms 169784 KB Output is correct
9 Correct 202 ms 166704 KB Output is correct
10 Correct 123 ms 119560 KB Output is correct
11 Correct 129 ms 119060 KB Output is correct
12 Correct 148 ms 144704 KB Output is correct
13 Correct 170 ms 147664 KB Output is correct
14 Correct 113 ms 123204 KB Output is correct
15 Correct 178 ms 143988 KB Output is correct
16 Correct 161 ms 140032 KB Output is correct
17 Correct 148 ms 134456 KB Output is correct
18 Correct 183 ms 105224 KB Output is correct
19 Correct 80 ms 104780 KB Output is correct
20 Correct 104 ms 104840 KB Output is correct
21 Correct 99 ms 104700 KB Output is correct
22 Correct 111 ms 104736 KB Output is correct
23 Correct 131 ms 104960 KB Output is correct
24 Correct 217 ms 162756 KB Output is correct
25 Correct 232 ms 163588 KB Output is correct
26 Correct 202 ms 161896 KB Output is correct
27 Correct 150 ms 122700 KB Output is correct
28 Correct 363 ms 129892 KB Output is correct
29 Correct 153 ms 113216 KB Output is correct