Submission #49092

#	Time	Username	Problem	Language	Result	Execution time	Memory
49092		tmwilliamlin168	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	296 ms	162884 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void ins(string &s) {
	char c=getchar_unlocked();
	while(c>='A'&&c<='Z') {
		s+=c;
		c=getchar_unlocked();
	}
}
inline void out(int x) {
	int rev=x, count = 0;
	if(x == 0) {
putchar_unlocked('0');
putchar_unlocked('\n');
return;
}
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
	putchar_unlocked('\n');
}

const int mxN1=1e5, mxN2=2e6;
int n, m, enc[256], ans[mxN1], ft[mxN2+1];
string ss[mxN1];
vector<int> pts[mxN2];

struct query {
	int i, l, r, w;
};
vector<query> queries[mxN2+1];

struct trie {
	int sz=1, c[mxN2][4], dt, st[mxN2], en[mxN2];
	inline void ins(string &s) {
		for(int i=0, u=0; i<s.size(); ++i) {
			if(!c[u][enc[s[i]]])
				c[u][enc[s[i]]]=sz++;
			u=c[u][enc[s[i]]];
		}
	}
	inline void dfs1(int u=0) {
		st[u]=dt++;
		for(int i=0; i<4; ++i)
			if(c[u][i])
				dfs1(c[u][i]);
		en[u]=dt;
	}
	inline int gi(string &s) {
		int u=0;
		for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
			if(!c[u][enc[s[i]]])
				return -1;
		return u;
	}
} t[2];

inline void upd(int i, int x) {
	for(++i; i<=mxN2; i+=i&-i)
		ft[i]+=x;
}

inline int qry(int i) {
	int r=0;
	for(; i; i-=i&-i)
		r+=ft[i];
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	enc['A']=0;
	enc['G']=1;
	enc['C']=2;
	enc['U']=3;
	n=in(), m=in();
	for(int i=0; i<n; ++i) {
		ins(ss[i]);
		t[0].ins(ss[i]);
		reverse(ss[i].begin(), ss[i].end());
		t[1].ins(ss[i]);
	}
	t[0].dfs1();
	t[1].dfs1();
	for(int i=0; i<n; ++i) {
		int y=t[1].st[t[1].gi(ss[i])];
		reverse(ss[i].begin(), ss[i].end());
		int x=t[0].st[t[0].gi(ss[i])];
		pts[y].push_back(x);
	}
	for(int i=0; i<m; ++i) {
		string p, q;
		ins(p), ins(q), reverse(q.begin(), q.end());
		int pi=t[0].gi(p), qi=t[1].gi(q);
		if(pi==-1||qi==-1)
			continue;
		queries[t[1].st[qi]].push_back({i, t[0].st[pi], t[0].en[pi], -1});
		queries[t[1].en[qi]].push_back({i, t[0].st[pi], t[0].en[pi], 1});
	}
	for(int i=0; i<mxN2; ++i) {
		for(int x : pts[i])
			upd(x, 1);
		for(query q : queries[i+1])
			ans[q.i]+=q.w*(qry(q.r)-qry(q.l));
	}
	for(int i=0; i<m; ++i)
		out(ans[i]);
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie::ins(std::__cxx11::string&)':
selling_rna.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, u=0; i<s.size(); ++i) {
                     ~^~~~~~~~~
selling_rna.cpp:67:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(!c[u][enc[s[i]]])
                     ^
selling_rna.cpp:68:18: warning: array subscript has type 'char' [-Wchar-subscripts]
     c[u][enc[s[i]]]=sz++;
                  ^
selling_rna.cpp:69:19: warning: array subscript has type 'char' [-Wchar-subscripts]
    u=c[u][enc[s[i]]];
                   ^
selling_rna.cpp: In member function 'int trie::gi(std::__cxx11::string&)':
selling_rna.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
                ~^~~~~~~~~
selling_rna.cpp:81:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   for(int i=0; i<s.size(); u=c[u][enc[s[i]]], ++i)
                                           ^
selling_rna.cpp:82:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(!c[u][enc[s[i]]])
                     ^

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