oj.uz

Submission #598078

# Submission time Handle Problem Language Result Execution time Memory
598078 2022-07-17T14:13:14 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 354120 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 = 2e6+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 c = query(r[abs(x)]) - query(l[abs(x)]);
			if(x>0)ans[x]+=c;
			else ans[x]-=c;
		}
	}*/
	
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 141260 KB Output is correct
2 Correct 65 ms 141172 KB Output is correct
3 Correct 66 ms 141280 KB Output is correct
4 Correct 68 ms 141220 KB Output is correct
5 Correct 76 ms 141248 KB Output is correct
6 Correct 69 ms 141384 KB Output is correct
7 Correct 66 ms 141260 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 190212 KB Output is correct
2 Correct 283 ms 191824 KB Output is correct
3 Correct 226 ms 193576 KB Output is correct
4 Correct 273 ms 191408 KB Output is correct
5 Runtime error 232 ms 354120 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 144412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 141260 KB Output is correct
2 Correct 65 ms 141172 KB Output is correct
3 Correct 66 ms 141280 KB Output is correct
4 Correct 68 ms 141220 KB Output is correct
5 Correct 76 ms 141248 KB Output is correct
6 Correct 69 ms 141384 KB Output is correct
7 Correct 66 ms 141260 KB Output is correct
8 Correct 171 ms 190212 KB Output is correct
9 Correct 283 ms 191824 KB Output is correct
10 Correct 226 ms 193576 KB Output is correct
11 Correct 273 ms 191408 KB Output is correct
12 Runtime error 232 ms 354120 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -