Submission #4471

#	Time	Username	Problem	Language	Result	Execution time	Memory
4471		tncks0121	사냥꾼 (KOI13_hunter)	C++98	100 / 100	80 ms	1868 KiB

hunter

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int SZ = 100005;

int N, M; ll L;
ll X[SZ];
int res;

int main() {
	int i, j, k;

	scanf("%d%d%lld", &M, &N, &L);
	for(i = 1; i <= M; i++) scanf("%lld", X+i);
	sort(X+1, X+M+1);
	M = unique(X+1, X+M+1) - (X+1);

	for(i = 1; i <= N; i++) {
		ll x, y; scanf("%lld%lld", &x, &y);
		if(y > L) continue;
		/*
		x + y - L <= X[k] <= x - y + L
		*/

		int a = -1, b = -5;
		int left, right;

		left = 1, right = M;
		while(left <= right) {
			int mid = (left + right) >> 1;
			if(x + y - L <= X[mid]) {
				a = mid;
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}

		left = 1, right = M;
		while(left <= right) {
			int mid = (left + right) >> 1;
			if(x - y + L >= X[mid]) {
				b = mid;
				left = mid + 1;
			}else {
				right = mid - 1;
			}
		}

		if(a > 0 && b > 0 && a <= b) ++res;
	}

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

• Subtask 1: 10 / 10
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30