oj.uz

Submission #399038

# Submission time Handle Problem Language Result Execution time Memory
399038 2021-05-05T07:07:28 Z keta_tsimakuridze Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 480 ms 429456 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ends endss
using namespace std;
const int N=1e5+5,mod=1e9+7;
int t,n,m,pwr[N],ans[N],tree[N],aft[20*N][5],cur,timer,tmin[20*N],tmout[20*N],L,R;
vector<pair<int,pair<int,int> > >Q[N],P[N];;
vector<int> ends[20*N][2];
string s[N],s1[N];
int get(char c){
	if(c=='A') return 1;
	if(c=='G') return 2;
	if(c=='U') return 3;
	return 0;
}
void add(string s,int ind,int f){
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) cur++,aft[u][get(s[i])]=cur;
		
		u=aft[u][get(s[i])];	ends[u][f].push_back(ind);
	}

}
void dfs(int u){
	timer++;
	tmin[u] = timer;
	for(int i=0;i<4;i++){
		if(aft[u][i]) dfs(aft[u][i]);
	}
	tmout[u]=timer;
}
void find(string s){
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) return;
		u=aft[u][get(s[i])];
	}	
	if(!ends[u][0].size()){
		L=n+1;
		R=0; return;
	}
	L = ends[u][0][0],R=ends[u][0].back();
}
void find1(string s,int ind){
	if(L>R) return ; 
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) return;
		u=aft[u][get(s[i])];
	}

	int l=0,r=ends[u][1].size(),en=-1,st=n+1;r--;
	while(l<=r){
		int mid=(l+r)/2;
		if(ends[u][1][mid]>=L) {
			st=mid;
			r=mid-1;
		}
		else l=mid+1;
	}	
	 l=0,r=ends[u][1].size();r--;
	while(l<=r){
		int mid=(l+r)/2;
		if(ends[u][1][mid]<=R) {
			en=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	if(st<=en) 	ans[ind]=en-st+1;
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// t=1;
	cin >> n >> m;
	int mx = 0;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	sort(s+1,s+n+1); 
	for(int i=1;i<=n;i++){
		add(s[i],i,0); 
		reverse(s[i].begin(),s[i].end()); 
		add(s[i],i,1);
	}

	string pref,suff;
	for(int i=1;i<=m;i++){
	
		cin>>pref>>suff;
		L=n+1; R=0;
		find(pref);
		reverse(suff.begin(),suff.end());
	
		find1(suff,i);
	cout<<ans[i]<<" ";
	}
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int, int)':
selling_rna.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: In function 'void find(std::string)':
selling_rna.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: In function 'void find1(std::string, int)':
selling_rna.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:74:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 |  main(){
      |       ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:78:6: warning: unused variable 'mx' [-Wunused-variable]
   78 |  int mx = 0;
      |      ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 105256 KB Output is correct
2 Correct 56 ms 105116 KB Output is correct
3 Correct 57 ms 105140 KB Output is correct
4 Correct 57 ms 105152 KB Output is correct
5 Correct 57 ms 105156 KB Output is correct
6 Correct 55 ms 105208 KB Output is correct
7 Correct 56 ms 105180 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 222860 KB Output is correct
2 Correct 368 ms 216692 KB Output is correct
3 Correct 293 ms 220996 KB Output is correct
4 Correct 283 ms 215708 KB Output is correct
5 Runtime error 480 ms 429456 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 107196 KB Output is correct
2 Correct 90 ms 107048 KB Output is correct
3 Correct 95 ms 107076 KB Output is correct
4 Correct 88 ms 106968 KB Output is correct
5 Correct 90 ms 106948 KB Output is correct
6 Correct 97 ms 106948 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 105256 KB Output is correct
2 Correct 56 ms 105116 KB Output is correct
3 Correct 57 ms 105140 KB Output is correct
4 Correct 57 ms 105152 KB Output is correct
5 Correct 57 ms 105156 KB Output is correct
6 Correct 55 ms 105208 KB Output is correct
7 Correct 56 ms 105180 KB Output is correct
8 Correct 346 ms 222860 KB Output is correct
9 Correct 368 ms 216692 KB Output is correct
10 Correct 293 ms 220996 KB Output is correct
11 Correct 283 ms 215708 KB Output is correct
12 Runtime error 480 ms 429456 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -