oj.uz

Submission #162595

# Submission time Handle Problem Language Result Execution time Memory
162595 2019-11-09T01:21:12 Z HungAnhGoldIBO2020 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1173 ms 1048576 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')]){
			cnt++;
			suf[now].go[(int)(s[i]-'A')]=cnt;
		}
		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 427 ms 532856 KB Output is correct
2 Correct 425 ms 532680 KB Output is correct
3 Correct 429 ms 532592 KB Output is correct
4 Correct 429 ms 532768 KB Output is correct
5 Correct 427 ms 532592 KB Output is correct
6 Correct 422 ms 532832 KB Output is correct
7 Correct 425 ms 532704 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 600508 KB Output is correct
2 Correct 718 ms 597240 KB Output is correct
3 Correct 614 ms 550072 KB Output is correct
4 Correct 580 ms 549624 KB Output is correct
5 Runtime error 1173 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 534208 KB Output is correct
2 Correct 480 ms 533816 KB Output is correct
3 Correct 472 ms 534008 KB Output is correct
4 Correct 467 ms 533716 KB Output is correct
5 Correct 646 ms 533848 KB Output is correct
6 Correct 490 ms 533920 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 532856 KB Output is correct
2 Correct 425 ms 532680 KB Output is correct
3 Correct 429 ms 532592 KB Output is correct
4 Correct 429 ms 532768 KB Output is correct
5 Correct 427 ms 532592 KB Output is correct
6 Correct 422 ms 532832 KB Output is correct
7 Correct 425 ms 532704 KB Output is correct
8 Correct 713 ms 600508 KB Output is correct
9 Correct 718 ms 597240 KB Output is correct
10 Correct 614 ms 550072 KB Output is correct
11 Correct 580 ms 549624 KB Output is correct
12 Runtime error 1173 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -