oj.uz

Submission #598083

# Submission time Handle Problem Language Result Execution time Memory
598083 2022-07-17T14:22:55 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 337 ms 352440 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 = 4e6+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])if(x)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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 282096 KB Output is correct
2 Correct 146 ms 282104 KB Output is correct
3 Correct 140 ms 282144 KB Output is correct
4 Correct 124 ms 282264 KB Output is correct
5 Correct 133 ms 282156 KB Output is correct
6 Correct 148 ms 282060 KB Output is correct
7 Correct 131 ms 282060 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 338660 KB Output is correct
2 Correct 312 ms 336844 KB Output is correct
3 Correct 294 ms 331896 KB Output is correct
4 Correct 318 ms 330000 KB Output is correct
5 Correct 307 ms 351460 KB Output is correct
6 Correct 337 ms 352440 KB Output is correct
7 Correct 261 ms 284808 KB Output is correct
8 Correct 324 ms 309196 KB Output is correct
9 Correct 322 ms 307380 KB Output is correct
10 Correct 248 ms 309324 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 286264 KB Output is correct
2 Correct 174 ms 284764 KB Output is correct
3 Correct 157 ms 286044 KB Output is correct
4 Correct 171 ms 285208 KB Output is correct
5 Correct 167 ms 285064 KB Output is correct
6 Correct 158 ms 285800 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 282096 KB Output is correct
2 Correct 146 ms 282104 KB Output is correct
3 Correct 140 ms 282144 KB Output is correct
4 Correct 124 ms 282264 KB Output is correct
5 Correct 133 ms 282156 KB Output is correct
6 Correct 148 ms 282060 KB Output is correct
7 Correct 131 ms 282060 KB Output is correct
8 Correct 300 ms 338660 KB Output is correct
9 Correct 312 ms 336844 KB Output is correct
10 Correct 294 ms 331896 KB Output is correct
11 Correct 318 ms 330000 KB Output is correct
12 Correct 307 ms 351460 KB Output is correct
13 Correct 337 ms 352440 KB Output is correct
14 Correct 261 ms 284808 KB Output is correct
15 Correct 324 ms 309196 KB Output is correct
16 Correct 322 ms 307380 KB Output is correct
17 Correct 248 ms 309324 KB Output is correct
18 Correct 167 ms 286264 KB Output is correct
19 Correct 174 ms 284764 KB Output is correct
20 Correct 157 ms 286044 KB Output is correct
21 Correct 171 ms 285208 KB Output is correct
22 Correct 167 ms 285064 KB Output is correct
23 Correct 158 ms 285800 KB Output is correct
24 Correct 309 ms 334756 KB Output is correct
25 Correct 336 ms 335692 KB Output is correct
26 Correct 292 ms 333880 KB Output is correct
27 Correct 313 ms 328908 KB Output is correct
28 Correct 328 ms 304464 KB Output is correct
29 Correct 258 ms 293288 KB Output is correct