oj.uz

Submission #49092

# Submission time Handle Problem Language Result Execution time Memory
49092 2018-05-22T03:07:02 Z tmwilliamlin168 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 296 ms 162884 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 97620 KB Output is correct
2 Correct 99 ms 97636 KB Output is correct
3 Correct 94 ms 97712 KB Output is correct
4 Correct 101 ms 97712 KB Output is correct
5 Correct 100 ms 97804 KB Output is correct
6 Correct 102 ms 97804 KB Output is correct
7 Correct 95 ms 97804 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 147380 KB Output is correct
2 Correct 273 ms 147380 KB Output is correct
3 Correct 258 ms 154160 KB Output is correct
4 Correct 250 ms 154160 KB Output is correct
5 Correct 296 ms 161924 KB Output is correct
6 Correct 296 ms 162884 KB Output is correct
7 Correct 159 ms 162884 KB Output is correct
8 Correct 272 ms 162884 KB Output is correct
9 Correct 246 ms 162884 KB Output is correct
10 Correct 215 ms 162884 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 162884 KB Output is correct
2 Correct 107 ms 162884 KB Output is correct
3 Correct 108 ms 162884 KB Output is correct
4 Correct 105 ms 162884 KB Output is correct
5 Correct 110 ms 162884 KB Output is correct
6 Correct 117 ms 162884 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 97620 KB Output is correct
2 Correct 99 ms 97636 KB Output is correct
3 Correct 94 ms 97712 KB Output is correct
4 Correct 101 ms 97712 KB Output is correct
5 Correct 100 ms 97804 KB Output is correct
6 Correct 102 ms 97804 KB Output is correct
7 Correct 95 ms 97804 KB Output is correct
8 Correct 247 ms 147380 KB Output is correct
9 Correct 273 ms 147380 KB Output is correct
10 Correct 258 ms 154160 KB Output is correct
11 Correct 250 ms 154160 KB Output is correct
12 Correct 296 ms 161924 KB Output is correct
13 Correct 296 ms 162884 KB Output is correct
14 Correct 159 ms 162884 KB Output is correct
15 Correct 272 ms 162884 KB Output is correct
16 Correct 246 ms 162884 KB Output is correct
17 Correct 215 ms 162884 KB Output is correct
18 Correct 108 ms 162884 KB Output is correct
19 Correct 107 ms 162884 KB Output is correct
20 Correct 108 ms 162884 KB Output is correct
21 Correct 105 ms 162884 KB Output is correct
22 Correct 110 ms 162884 KB Output is correct
23 Correct 117 ms 162884 KB Output is correct
24 Correct 249 ms 162884 KB Output is correct
25 Correct 254 ms 162884 KB Output is correct
26 Correct 242 ms 162884 KB Output is correct
27 Correct 261 ms 162884 KB Output is correct
28 Correct 235 ms 162884 KB Output is correct
29 Correct 139 ms 162884 KB Output is correct