oj.uz

Submission #162596

# Submission time Handle Problem Language Result Execution time Memory
162596 2019-11-09T01:23:50 Z HungAnhGoldIBO2020 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 858 ms 598848 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+2;
const int inf=1e9+7;
struct node{
	int go[26],l=0,r=0;
} pre[N];
struct node1{
	int go[26];
	vector<int> idx;
} suf[N];
pair<int,int> lis;
string x[N];
int cnt=0,cnt1=0;
void insert_pre(string s,int idx1){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!pre[now].go[(int)(s[i]-'A')]){
			cnt++;
			pre[now].go[(int)(s[i]-'A')]=cnt;
		}
		now=pre[now].go[(int)(s[i]-'A')];
		if(!pre[now].l){
			pre[now].l=idx1;
		}
		pre[now].r=idx1;
	}
}
void insert_suf(string s,int idx2){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!suf[now].go[(int)(s[i]-'A')]){
			cnt1++;
			suf[now].go[(int)(s[i]-'A')]=cnt1;
		}
		now=suf[now].go[(int)(s[i]-'A')];
		suf[now].idx.push_back(idx2);
	}
}
void get_range(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!pre[now].go[(int)(s[i]-'A')]){
			lis.first=inf;
			lis.second=-inf;
			return;
		}
		now=pre[now].go[(int)(s[i]-'A')];
	}
	lis.first=pre[now].l;
	lis.second=pre[now].r;
}
int get_ans(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!suf[now].go[(int)(s[i]-'A')]){
			return 0;
		}
		now=suf[now].go[(int)(s[i]-'A')];
	}
	int num1=upper_bound(suf[now].idx.begin(),suf[now].idx.end(),lis.second)-suf[now].idx.begin()-1;
	int num2=lower_bound(suf[now].idx.begin(),suf[now].idx.end(),lis.first)-suf[now].idx.begin()-1;
//	cout<<now<<" cac"<<endl;
//	for(int i:suf[now].idx){
//		cout<<i<<' ';
//	}
//	cout<<"lon "<<num1<<' '<<num2<<endl;
	return num1-num2;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,q,i,j,k,l;
	cin>>n>>q;
	for(i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+n);
	string t,t1;
	for(i=1;i<=n;i++){
		t=x[i];
		insert_pre(t,i);
		reverse(t.begin(),t.end());
		insert_suf(t,i);
	}
	for(i=1;i<=q;i++){
		cin>>t>>t1;
		get_range(t);
		if(lis.second==-inf){
			cout<<"0\n";
			continue;
		}
		reverse(t1.begin(),t1.end());
		cout<<get_ans(t1)<<'\n';
	}
}

Compilation message

selling_rna.cpp: In function 'void insert_pre(std::__cxx11::string, int)':
selling_rna.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'void insert_suf(std::__cxx11::string, int)':
selling_rna.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'void get_range(std::__cxx11::string)':
selling_rna.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'int get_ans(std::__cxx11::string)':
selling_rna.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
  int n,q,i,j,k,l;
            ^
selling_rna.cpp:73:14: warning: unused variable 'k' [-Wunused-variable]
  int n,q,i,j,k,l;
              ^
selling_rna.cpp:73:16: warning: unused variable 'l' [-Wunused-variable]
  int n,q,i,j,k,l;
                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 532648 KB Output is correct
2 Correct 477 ms 532572 KB Output is correct
3 Correct 443 ms 532720 KB Output is correct
4 Correct 452 ms 532596 KB Output is correct
5 Correct 446 ms 532668 KB Output is correct
6 Correct 455 ms 532588 KB Output is correct
7 Correct 448 ms 532684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 598848 KB Output is correct
2 Correct 720 ms 595636 KB Output is correct
3 Correct 598 ms 548600 KB Output is correct
4 Correct 651 ms 548116 KB Output is correct
5 Correct 772 ms 574788 KB Output is correct
6 Correct 752 ms 575380 KB Output is correct
7 Correct 582 ms 548156 KB Output is correct
8 Correct 858 ms 569024 KB Output is correct
9 Correct 740 ms 564808 KB Output is correct
10 Correct 651 ms 562132 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 533456 KB Output is correct
2 Correct 514 ms 533392 KB Output is correct
3 Correct 486 ms 533528 KB Output is correct
4 Correct 482 ms 533340 KB Output is correct
5 Correct 488 ms 533548 KB Output is correct
6 Correct 473 ms 533444 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 532648 KB Output is correct
2 Correct 477 ms 532572 KB Output is correct
3 Correct 443 ms 532720 KB Output is correct
4 Correct 452 ms 532596 KB Output is correct
5 Correct 446 ms 532668 KB Output is correct
6 Correct 455 ms 532588 KB Output is correct
7 Correct 448 ms 532684 KB Output is correct
8 Correct 715 ms 598848 KB Output is correct
9 Correct 720 ms 595636 KB Output is correct
10 Correct 598 ms 548600 KB Output is correct
11 Correct 651 ms 548116 KB Output is correct
12 Correct 772 ms 574788 KB Output is correct
13 Correct 752 ms 575380 KB Output is correct
14 Correct 582 ms 548156 KB Output is correct
15 Correct 858 ms 569024 KB Output is correct
16 Correct 740 ms 564808 KB Output is correct
17 Correct 651 ms 562132 KB Output is correct
18 Correct 498 ms 533456 KB Output is correct
19 Correct 514 ms 533392 KB Output is correct
20 Correct 486 ms 533528 KB Output is correct
21 Correct 482 ms 533340 KB Output is correct
22 Correct 488 ms 533548 KB Output is correct
23 Correct 473 ms 533444 KB Output is correct
24 Correct 734 ms 589420 KB Output is correct
25 Correct 724 ms 589688 KB Output is correct
26 Correct 745 ms 588664 KB Output is correct
27 Correct 572 ms 549368 KB Output is correct
28 Correct 676 ms 555136 KB Output is correct
29 Correct 581 ms 541112 KB Output is correct