oj.uz

Submission #598079

# Submission time Handle Problem Language Result Execution time Memory
598079 2022-07-17T14:13:37 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 626764 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 563916 KB Output is correct
2 Correct 249 ms 563900 KB Output is correct
3 Correct 246 ms 563960 KB Output is correct
4 Correct 261 ms 564024 KB Output is correct
5 Correct 262 ms 563896 KB Output is correct
6 Correct 258 ms 563992 KB Output is correct
7 Correct 284 ms 563868 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 613552 KB Output is correct
2 Correct 546 ms 611436 KB Output is correct
3 Correct 477 ms 613084 KB Output is correct
4 Correct 581 ms 610992 KB Output is correct
5 Correct 543 ms 624656 KB Output is correct
6 Correct 529 ms 626764 KB Output is correct
7 Correct 437 ms 571708 KB Output is correct
8 Correct 544 ms 591412 KB Output is correct
9 Correct 526 ms 590824 KB Output is correct
10 Correct 454 ms 592072 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1609 ms 567220 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 563916 KB Output is correct
2 Correct 249 ms 563900 KB Output is correct
3 Correct 246 ms 563960 KB Output is correct
4 Correct 261 ms 564024 KB Output is correct
5 Correct 262 ms 563896 KB Output is correct
6 Correct 258 ms 563992 KB Output is correct
7 Correct 284 ms 563868 KB Output is correct
8 Correct 454 ms 613552 KB Output is correct
9 Correct 546 ms 611436 KB Output is correct
10 Correct 477 ms 613084 KB Output is correct
11 Correct 581 ms 610992 KB Output is correct
12 Correct 543 ms 624656 KB Output is correct
13 Correct 529 ms 626764 KB Output is correct
14 Correct 437 ms 571708 KB Output is correct
15 Correct 544 ms 591412 KB Output is correct
16 Correct 526 ms 590824 KB Output is correct
17 Correct 454 ms 592072 KB Output is correct
18 Execution timed out 1609 ms 567220 KB Time limit exceeded
19 Halted 0 ms 0 KB -