답안 #4471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4471	2013-10-07T15:57:49 Z	tncks0121	사냥꾼 (KOI13_hunter)	C++	100 / 100	80 ms	1868 KB

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

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

Subtask #2

17.0 / 17.0

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

Subtask #3

21.0 / 21.0

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

Subtask #4

22.0 / 22.0

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

Subtask #5

30.0 / 30.0

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