답안 #4925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4925	2014-01-14T04:20:01 Z	Qwaz	사냥꾼 (KOI13_hunter)	C++	100 / 100	80 ms	2260 KB

hunter

#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX=100020, INF=1234567890;

int m, n, len, pos[MAX], x[MAX], y[MAX];

void input(){
	scanf("%d%d%d", &m, &n, &len);

	int i;
	for(i=0; i<m; i++)
		scanf("%d", &pos[i]);

	for(i=0; i<n; i++)
		scanf("%d%d", &x[i], &y[i]);
}

int res;

void solve(){
	sort(pos, pos+m);
	pos[m++] = INF;

	int i;
	for(i=0; i<n; i++){
		if(y[i] > len) continue;

		int f, s, l, r, mid;
		l = 0;
		r = m-1;
		while(l <= r){
			mid = (l+r)>>1;
			if(pos[mid] >= x[i]+y[i]-len)
				r = mid-1;
			else
				l = mid+1;
		}
		f = r+1;

		l = 0;
		r = m-1;
		while(l <= r){
			mid = (l+r)>>1;
			if(pos[mid] <= x[i]-y[i]+len)
				l = mid+1;
			else
				r = mid-1;
		}
		s = l-1;

		if(f <= s) res++;
	}

	printf("%d\n", res);
}

int main(){
	input();

	solve();

	return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2260 KB	Output is correct
2	Correct	0 ms	2260 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2260 KB	Output is correct
2	Correct	0 ms	2260 KB	Output is correct
3	Correct	0 ms	2260 KB	Output is correct
4	Correct	0 ms	2260 KB	Output is correct
5	Correct	0 ms	2260 KB	Output is correct
6	Correct	0 ms	2260 KB	Output is correct
7	Correct	0 ms	2260 KB	Output is correct
8	Correct	0 ms	2260 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2260 KB	Output is correct
2	Correct	0 ms	2260 KB	Output is correct
3	Correct	0 ms	2260 KB	Output is correct
4	Correct	0 ms	2260 KB	Output is correct
5	Correct	0 ms	2260 KB	Output is correct
6	Correct	0 ms	2260 KB	Output is correct
7	Correct	0 ms	2260 KB	Output is correct
8	Correct	0 ms	2260 KB	Output is correct
9	Correct	0 ms	2260 KB	Output is correct
10	Correct	0 ms	2260 KB	Output is correct

Subtask #4

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2260 KB	Output is correct
2	Correct	0 ms	2260 KB	Output is correct
3	Correct	0 ms	2260 KB	Output is correct
4	Correct	0 ms	2260 KB	Output is correct
5	Correct	0 ms	2260 KB	Output is correct
6	Correct	0 ms	2260 KB	Output is correct
7	Correct	0 ms	2260 KB	Output is correct
8	Correct	0 ms	2260 KB	Output is correct
9	Correct	0 ms	2260 KB	Output is correct
10	Correct	0 ms	2260 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	2260 KB	Output is correct
2	Correct	48 ms	2260 KB	Output is correct
3	Correct	32 ms	2260 KB	Output is correct
4	Correct	64 ms	2260 KB	Output is correct
5	Correct	44 ms	2260 KB	Output is correct
6	Correct	68 ms	2260 KB	Output is correct
7	Correct	64 ms	2260 KB	Output is correct
8	Correct	72 ms	2260 KB	Output is correct
9	Correct	72 ms	2260 KB	Output is correct
10	Correct	80 ms	2260 KB	Output is correct