Submission #101328

#	Time	Username	Problem	Language	Result	Execution time	Memory
101328		autumn_eel	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	323 ms	179544 KiB

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+1;
}

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 (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:74: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);
   ~~~~~^~~~~~~~
selling_rna.cpp:84: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:85: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: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40