oj.uz

Submission #4925

# Submission time Handle Problem Language Result Execution time Memory
4925 2014-01-14T04:20:01 Z Qwaz 사냥꾼 (KOI13_hunter) C++
100 / 100
 80 ms 2260 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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