oj.uz

Submission #598080

# Submission time Handle Problem Language Result Execution time Memory
598080 2022-07-17T14:14:12 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 624588 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 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 249 ms 564032 KB Output is correct
2 Correct 249 ms 563960 KB Output is correct
3 Correct 268 ms 563892 KB Output is correct
4 Correct 249 ms 563932 KB Output is correct
5 Correct 254 ms 563860 KB Output is correct
6 Correct 259 ms 563852 KB Output is correct
7 Correct 246 ms 563916 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 613640 KB Output is correct
2 Correct 561 ms 611436 KB Output is correct
3 Correct 496 ms 613128 KB Output is correct
4 Correct 552 ms 610972 KB Output is correct
5 Correct 563 ms 623680 KB Output is correct
6 Correct 581 ms 624588 KB Output is correct
7 Correct 408 ms 566564 KB Output is correct
8 Correct 567 ms 585620 KB Output is correct
9 Correct 561 ms 585236 KB Output is correct
10 Correct 461 ms 588724 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 564032 KB Output is correct
2 Correct 249 ms 563960 KB Output is correct
3 Correct 268 ms 563892 KB Output is correct
4 Correct 249 ms 563932 KB Output is correct
5 Correct 254 ms 563860 KB Output is correct
6 Correct 259 ms 563852 KB Output is correct
7 Correct 246 ms 563916 KB Output is correct
8 Correct 462 ms 613640 KB Output is correct
9 Correct 561 ms 611436 KB Output is correct
10 Correct 496 ms 613128 KB Output is correct
11 Correct 552 ms 610972 KB Output is correct
12 Correct 563 ms 623680 KB Output is correct
13 Correct 581 ms 624588 KB Output is correct
14 Correct 408 ms 566564 KB Output is correct
15 Correct 567 ms 585620 KB Output is correct
16 Correct 561 ms 585236 KB Output is correct
17 Correct 461 ms 588724 KB Output is correct
18 Execution timed out 1606 ms 567160 KB Time limit exceeded
19 Halted 0 ms 0 KB -