Submission #101330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101330	2019-03-18T13:23:25 Z	autumn_eel	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	478 ms	195960 KB

selling_rna

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;

int bit[3000000];

void add(int k,int x){
	k++;
	while(k<3000000){
		bit[k]+=x;
		k+=k&-k;
	}
}
int sum(int k){
	int res=0;
	while(k){
		res+=bit[k];
		k-=k&-k;
	}
	return res;
}
int sum(int l,int r){
	return sum(r)-sum(l);
}

int getId(char c){
	if(c=='A')return 0;
	if(c=='G')return 1;
	if(c=='C')return 2;
	return 3;
}

struct node{
	node*nx[4];
	int l,r;
}pool[3000000];

node*root1=&pool[0],*root2=&pool[1];
int pointer=2;

node*add(node*root,string&s){
	node*x=root;
	for(char c:s){
		if(x->nx[getId(c)]==NULL){
			x->nx[getId(c)]=&pool[pointer++];
		}
		x=x->nx[getId(c)];
	}
	return x;
}

int cnt=0;
void dfs(node*t){
	t->l=cnt++;
	rep(i,4){
		if(t->nx[i])dfs(t->nx[i]);
	}
	t->r=cnt;
}

char S[200000];
string s[200000],p[200000],q[200000];

struct st{
	int ty,l,r;
};
vector<st>query[3000000];
int ans[200000];

int main(){
	int n,m;scanf("%d%d",&n,&m);
	rep(i,n){
		scanf("%s",S);
		s[i]=S;
		add(root1,s[i]);
		reverse(s[i].begin(),s[i].end());
		add(root2,s[i]);
		reverse(s[i].begin(),s[i].end());
	}
	rep(i,m){
		scanf("%s",S);p[i]=S;
		scanf("%s",S);q[i]=S;
		add(root1,p[i]);
		reverse(q[i].begin(),q[i].end());
		add(root2,q[i]);
	}
	dfs(root1);
	dfs(root2);
	vector<st>v;
	rep(i,m){
		node*a=add(root1,p[i]),*b=add(root2,q[i]);
		query[a->l].push_back({i,b->l,b->r});
		query[a->r].push_back({i+m,b->l,b->r});
	}
	rep(i,n){
		int a=add(root1,s[i])->l;
		reverse(s[i].begin(),s[i].end());
		int b=add(root2,s[i])->l;
		reverse(s[i].begin(),s[i].end());
		query[a].push_back({-1,b,b+1});
	}
	rep(i,3000000){
		for(auto&s:query[i]){
			if(s.ty>=0){
				int res=sum(s.l,s.r);
				if(s.ty<m)ans[s.ty]-=res;
				else ans[s.ty-m]+=res;
			}
			else{
				add(s.l,1);
			}
		}
	}
	rep(i,m){
		printf("%d\n",ans[i]);
	}
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:72:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%d%d",&n,&m);
          ~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);
   ~~~~~^~~~~~~~
selling_rna.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);p[i]=S;
   ~~~~~^~~~~~~~
selling_rna.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);q[i]=S;
   ~~~~~^~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	89720 KB	Output is correct
2	Correct	89 ms	89744 KB	Output is correct
3	Correct	100 ms	89720 KB	Output is correct
4	Correct	96 ms	89720 KB	Output is correct
5	Correct	114 ms	89720 KB	Output is correct
6	Correct	98 ms	89720 KB	Output is correct
7	Correct	90 ms	89592 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	306 ms	177908 KB	Output is correct
2	Correct	312 ms	176096 KB	Output is correct
3	Correct	298 ms	171772 KB	Output is correct
4	Correct	313 ms	168180 KB	Output is correct
5	Correct	478 ms	194368 KB	Output is correct
6	Correct	435 ms	195960 KB	Output is correct
7	Correct	202 ms	97272 KB	Output is correct
8	Correct	351 ms	156440 KB	Output is correct
9	Correct	311 ms	146900 KB	Output is correct
10	Correct	253 ms	143424 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	92232 KB	Output is correct
2	Correct	118 ms	91468 KB	Output is correct
3	Correct	137 ms	92376 KB	Output is correct
4	Correct	110 ms	91760 KB	Output is correct
5	Correct	113 ms	92152 KB	Output is correct
6	Correct	125 ms	92444 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	89720 KB	Output is correct
2	Correct	89 ms	89744 KB	Output is correct
3	Correct	100 ms	89720 KB	Output is correct
4	Correct	96 ms	89720 KB	Output is correct
5	Correct	114 ms	89720 KB	Output is correct
6	Correct	98 ms	89720 KB	Output is correct
7	Correct	90 ms	89592 KB	Output is correct
8	Correct	306 ms	177908 KB	Output is correct
9	Correct	312 ms	176096 KB	Output is correct
10	Correct	298 ms	171772 KB	Output is correct
11	Correct	313 ms	168180 KB	Output is correct
12	Correct	478 ms	194368 KB	Output is correct
13	Correct	435 ms	195960 KB	Output is correct
14	Correct	202 ms	97272 KB	Output is correct
15	Correct	351 ms	156440 KB	Output is correct
16	Correct	311 ms	146900 KB	Output is correct
17	Correct	253 ms	143424 KB	Output is correct
18	Correct	125 ms	92232 KB	Output is correct
19	Correct	118 ms	91468 KB	Output is correct
20	Correct	137 ms	92376 KB	Output is correct
21	Correct	110 ms	91760 KB	Output is correct
22	Correct	113 ms	92152 KB	Output is correct
23	Correct	125 ms	92444 KB	Output is correct
24	Correct	346 ms	168404 KB	Output is correct
25	Correct	341 ms	169980 KB	Output is correct
26	Correct	319 ms	166844 KB	Output is correct
27	Correct	311 ms	161144 KB	Output is correct
28	Correct	326 ms	114128 KB	Output is correct
29	Correct	183 ms	98592 KB	Output is correct