oj.uz

답안 #598081

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598081 2022-07-17T14:19:18 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 702 ms 1009456 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
int ndcnt = 0;
const int MAXN = 8e6+5;
int ch[4][MAXN];
vector<int>ids[MAXN],que[MAXN],pts[MAXN];
int tin[MAXN],tout[MAXN];
pii pt[MAXN];
void add(string s,int id){
	int v = 0;
	for(char x:s){
		int c = 0;
		if(x=='C')c=1;
		if(x=='G')c=2;
		if(x=='U')c=3;
		if(!ch[c][v])ch[c][v] = ++ndcnt;
		v = ch[c][v];
	}
	ids[v].push_back(id);
}
int timer = 1;
void dfs(int v){
	tin[v] = ++timer;
	for(int i=0;i<4;i++){
		if(ch[i][v])dfs(ch[i][v]);
	}
	tout[v] = timer;
	for(int x:ids[v]){
		if(x>0)pt[x].fi = tin[v];
		else pt[-x].se = tin[v];
		
	}
	
}
int find(string s){
	int v = 0;
	for(char x:s){
		//cout<<v<<'\n';
		int c = 0;
		if(x=='C')c=1;
		if(x=='G')c=2;
		if(x=='U')c=3;
		if(!ch[c][v])return -1;
		v = ch[c][v];
	}
	return v;
	
}
int bit[MAXN];
void upd(int pos,int val,int n){
	for(int i=pos;i<=n;i+=i&(-i))bit[i]+=val;
}
int query(int r){
   int res = 0;
	for(int i=r;i>0;i-=i&(-i))res+=bit[i];
    return res;
}
int main()
{
	//owo
	int n,m;
	cin>>n>>m;
	vector<string>s(n+1);
	vector<int>ans(m+1,0),l(m+1),r(m+1);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		add(s[i],i);
		reverse(s[i].begin(),s[i].end());
		add(s[i],-i);
	}
	dfs(0);
	//cout<<"pts"<<'\n';
	for(int i=1;i<=n;i++){
		//cout<<pt[i].fi<<" "<<pt[i].se<<'\n';
		pts[pt[i].fi].push_back(pt[i].se);
	}
	//cout<<"rnage"<<'\n';
	for(int i=1;i<=m;i++){
		string p,q;
		cin>>p>>q;
		int v1 = find(p);
		reverse(q.begin(),q.end());
		int v2 = find(q);
		if(v1==-1 || v2==-1)continue;
	//	cout<<v1<<" "<<v2<<'\n';
		//cout<<i<<" "<<tin[v1]<<" "<<tout[v1]<<" "<<tin[v2]<<" "<<tout[v2]<<'\n'
		//for(int j=1;j<=n;j++)if(pt[j].fi >= tin[v1] && pt[j].se >= tin[v2] && pt[j].fi <= tout[v1] && pt[j].se <= tout[v2])ans[i]++;
		l[i] = tin[v2]-1;
		r[i] = tout[v2];
		que[tin[v1]-1].push_back(-i);
		que[tout[v1]].push_back(i);
	}
	for(int i=1;i<=timer;i++){
		for(int x:pts[i])upd(x,1,timer);
		for(int x:que[i]){
			int X = abs(x);
			//cout<<r[X]<<" "<<l[X]<<'\n';
			int c = query(r[X]) - query(l[X]);
			if(x>0)ans[x]+=c;
			else ans[x]-=c;
		}
	}
	
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 497 ms 930328 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 702 ms 1009456 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 568020 KB Output is correct
2 Runtime error 513 ms 933152 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 497 ms 930328 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -