Submission #933049

#	Time	Username	Problem	Language	Result	Execution time	Memory
933049		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	503 ms	1048576 KiB

selling_rna

#include <bits/stdc++.h>
#define endl "\n"
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long

using namespace std;

const int lim=1e5+5;

struct trie{
	trie *nxt[4]{};
	bool us=false;
	bitset<lim> bt;
} *pref, *suff;

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

void add(string s, int p, int x, bool B){
	if(p&1){
		trie *act=pref;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			if(B && act->us) act->bt.set(x);
		}
	}else{
		trie *act=suff;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			if(B && act->us) act->bt.set(x);
		}
	}
}

void actv(string s, int p){
	if(p&1){
		trie *act=pref;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) return;
			act=act->nxt[nx];
		}
		act->us=true;
	}else{
		trie *act=suff;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) return;
			act=act->nxt[nx];
		}
		act->us=true;
	}
}

int query(string a, string b){
	trie *bg=pref, *ed=suff;
	rep(i,0,a.size()){
		int nx=mp(a[i]);
		if(bg->nxt[nx]==NULL) return 0;
		bg=bg->nxt[nx];
	}
	rep(i,0,b.size()){
		int nx=mp(b[i]);
		if(ed->nxt[nx]==NULL) return 0;
		ed=ed->nxt[nx];
	}
	return ((bg->bt)&(ed->bt)).count();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string a[n], s;
	cin>>n>>q;
	pref=new trie;
	suff=new trie;
	rep(i,0,n){
		cin>>a[i];
		s=a[i];
		add(s,1,i,0);
		reverse(s.begin(),s.end());
		add(s,2,i,0);
	}
	pair<string, string> qry[q];
	rep(i,0,q){
		cin>>qry[i].fi>>qry[i].se;
		reverse(qry[i].se.begin(),qry[i].se.end());
		actv(qry[i].fi,1);
		actv(qry[i].se,2);
	}
	rep(i,0,n){
		s=a[i];
		add(s,1,i,1);
		reverse(s.begin(),s.end());
		add(s,2,i,1);
	}
	rep(i,0,q){
		cout<<query(qry[i].fi,qry[i].se)<<endl;
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::string, int, int, bool)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   30 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:30:3: note: in expansion of macro 'rep'
   30 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   38 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:38:3: note: in expansion of macro 'rep'
   38 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp: In function 'void actv(std::string, int)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   50 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:50:3: note: in expansion of macro 'rep'
   50 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   58 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:58:3: note: in expansion of macro 'rep'
   58 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp: In function 'int query(std::string, std::string)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   69 |  rep(i,0,a.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:69:2: note: in expansion of macro 'rep'
   69 |  rep(i,0,a.size()){
      |  ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   74 |  rep(i,0,b.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:74:2: note: in expansion of macro 'rep'
   74 |  rep(i,0,b.size()){
      |  ^~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40