oj.uz

Submission #963881

# Submission time Handle Problem Language Result Execution time Memory
963881 2024-04-16T01:17:58 Z LCJLY Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 302 ms 268708 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

struct trie{	
	trie *next[4];
	int in=0;
	int out=0;
	trie(){
		next[0]=next[1]=next[2]=next[3]=NULL;
	}	
};

auto rt=new trie();
auto rev=new trie();

int f(char a){
	if(a=='A') return 0;
	else if(a=='C') return 1;
	else if(a=='G') return 2;
	else return 3;
}

int ptr=0;

void dfs(trie*cur){
	cur->in=++ptr;
	for(int x=0;x<4;x++){
		if(cur->next[x]!=NULL){
			dfs(cur->next[x]);
		}
	}
	cur->out=ptr;
}

int fw[200005];

void upd(int x, int y){	
	while(x<200005){
		fw[x]+=y;
		x+=x&(-x);
	}	
}

int sum(int x){
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}
	return counter;
}

void rangeUpd(int x, int y, int c){		
	upd(x,c);
	upd(x+1,-c);
}

int query(int x, int y){
	return sum(y)-sum(x-1);
}

int ans[100005];
vector<array<int,4>>storage[200005];

void solve(){
	int n,m;
	cin >> n >> m;
	string arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
		//front
		auto cur=rt;
		for(int y=0;y<(int)arr[x].length();y++){
			int hold=f(arr[x][y]);
			if(cur->next[hold]==NULL) cur->next[hold]=new trie();
			cur=cur->next[hold];
		}
		
		//back
		string s=arr[x];
		reverse(s.begin(),s.end());
		cur=rev;
		for(int y=0;y<(int)s.length();y++){
			int hold=f(s[y]);
			if(cur->next[hold]==NULL) cur->next[hold]=new trie();
			cur=cur->next[hold];
		}
	}
	
	dfs(rt);
	ptr=0;
	dfs(rev);
	
	vector<pii>v;
	for(int x=0;x<n;x++){
		string s=arr[x];
		reverse(s.begin(),s.end());
		int sz=s.length();
		
		auto cur=rt;
		auto cur2=rev;
		for(int y=0;y<sz;y++){
			int hold=f(arr[x][y]);
			int hold2=f(s[y]);
			cur=cur->next[hold];
			cur2=cur2->next[hold2];
		}
		
		v.push_back({cur->in,cur2->in});
	}
	
	string temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		//front
		auto cur=rt;
		int sz=temp.size();
		bool amos=true;
		for(int y=0;y<sz;y++){
			int hold=f(temp[y]);
			if(cur->next[hold]==NULL){
				amos=false;
				break;
			}
			cur=cur->next[hold];
		}
		
		reverse(temp2.begin(),temp2.end());
		auto cur2=rev;
		sz=temp2.size();
		for(int y=0;y<sz;y++){
			int hold=f(temp2[y]);
			if(cur2->next[hold]==NULL){
				amos=false;
				break;
			}
			cur2=cur2->next[hold];
		}
		
		if(!amos) continue;
		else{
			storage[cur->in-1].push_back({cur2->in,cur2->out,x,-1});
			storage[cur->out].push_back({cur2->in,cur2->out,x,1});
		}
	}
	
	//l r index sign
	
	sort(v.begin(),v.end());
	int swp=0;
	for(int x=0;x<150005;x++){
		while(swp<(int)v.size()&&v[swp].first<=x){
			upd(v[swp].second,1);
			swp++;
		}
		
		for(auto it:storage[x]){
			ans[it[2]]+=(query(it[0],it[1])*it[3]);
		}
	}
	
	for(int x=0;x<m;x++){
		cout << ans[x] << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6792 KB Output is correct
3 Correct 2 ms 6752 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6788 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 302 ms 268708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14168 KB Output is correct
2 Correct 20 ms 11988 KB Output is correct
3 Correct 27 ms 13372 KB Output is correct
4 Correct 16 ms 11928 KB Output is correct
5 Correct 16 ms 11452 KB Output is correct
6 Correct 20 ms 12492 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6792 KB Output is correct
3 Correct 2 ms 6752 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6788 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Runtime error 302 ms 268708 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -