제출 #4925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4925		Qwaz	사냥꾼 (KOI13_hunter)	C++98	100 / 100	80 ms	2260 KiB

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 / 10
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30