oj.uz

답안 #49091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49091 2018-05-22T03:06:19 Z tmwilliamlin168 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 322 ms 191220 KB 
#include <bits/stdc++.h>
using namespace std;

#define getchar_unlocked getchar
#define putchar_unlocked putchar

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:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0, u=0; i<s.size(); ++i) {
                     ~^~~~~~~~~
selling_rna.cpp:70:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(!c[u][enc[s[i]]])
                     ^
selling_rna.cpp:71:18: warning: array subscript has type 'char' [-Wchar-subscripts]
     c[u][enc[s[i]]]=sz++;
                  ^
selling_rna.cpp:72: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:84: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:84: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:85:21: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(!c[u][enc[s[i]]])
                     ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 97528 KB Output is correct
2 Correct 93 ms 97636 KB Output is correct
3 Correct 93 ms 97636 KB Output is correct
4 Correct 98 ms 97704 KB Output is correct
5 Correct 92 ms 97744 KB Output is correct
6 Correct 100 ms 97768 KB Output is correct
7 Correct 92 ms 97856 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 147348 KB Output is correct
2 Correct 298 ms 147348 KB Output is correct
3 Correct 296 ms 154228 KB Output is correct
4 Correct 287 ms 155640 KB Output is correct
5 Correct 320 ms 168272 KB Output is correct
6 Correct 319 ms 171748 KB Output is correct
7 Correct 194 ms 171748 KB Output is correct
8 Correct 322 ms 171748 KB Output is correct
9 Correct 280 ms 171748 KB Output is correct
10 Correct 223 ms 171748 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 171748 KB Output is correct
2 Correct 109 ms 171748 KB Output is correct
3 Correct 111 ms 171748 KB Output is correct
4 Correct 109 ms 171748 KB Output is correct
5 Correct 107 ms 171748 KB Output is correct
6 Correct 111 ms 171748 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 97528 KB Output is correct
2 Correct 93 ms 97636 KB Output is correct
3 Correct 93 ms 97636 KB Output is correct
4 Correct 98 ms 97704 KB Output is correct
5 Correct 92 ms 97744 KB Output is correct
6 Correct 100 ms 97768 KB Output is correct
7 Correct 92 ms 97856 KB Output is correct
8 Correct 277 ms 147348 KB Output is correct
9 Correct 298 ms 147348 KB Output is correct
10 Correct 296 ms 154228 KB Output is correct
11 Correct 287 ms 155640 KB Output is correct
12 Correct 320 ms 168272 KB Output is correct
13 Correct 319 ms 171748 KB Output is correct
14 Correct 194 ms 171748 KB Output is correct
15 Correct 322 ms 171748 KB Output is correct
16 Correct 280 ms 171748 KB Output is correct
17 Correct 223 ms 171748 KB Output is correct
18 Correct 118 ms 171748 KB Output is correct
19 Correct 109 ms 171748 KB Output is correct
20 Correct 111 ms 171748 KB Output is correct
21 Correct 109 ms 171748 KB Output is correct
22 Correct 107 ms 171748 KB Output is correct
23 Correct 111 ms 171748 KB Output is correct
24 Correct 273 ms 173060 KB Output is correct
25 Correct 301 ms 178892 KB Output is correct
26 Correct 271 ms 180500 KB Output is correct
27 Correct 281 ms 191220 KB Output is correct
28 Correct 259 ms 191220 KB Output is correct
29 Correct 205 ms 191220 KB Output is correct