oj.uz

Submission #1162

# Submission time Handle Problem Language Result Execution time Memory
1162 2013-06-28T12:44:50 Z kriii 개구리 (KOI13_frog) C++
22 / 22
 265 ms 10140 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct point{int x,y,i;}P[100100];
vector<int> G[100100];

int N,R,D,V[100100],ANS; bool chk[100100];
int X[100100],Z=1<<17;
pair<int, int> B[1<<18];

bool cmp(const point& a, const point& b){return a.y > b.y;}

const int non = 0x7fffffff;
pair<int, int> out(int x, int y)
{
	x += Z; y += Z;
	pair<int, int> r(non,0);
	
	while (x < y){
		if (x & 1){r = min(r,B[x]); x++;}
		if (~y & 1){r = min(r,B[y]); y--;}
		x >>= 1; y >>= 1;
	} if (x == y) r = min(r,B[x]);

	return r;
}

void in(int x, pair<int, int> p)
{
	x += Z; B[x] = min(B[x], p); x >>= 1;
	while (x){
		B[x] = min(B[x*2],B[x*2+1]);
		x >>= 1;
	}
}

void make()
{
	int i,S,l,m,r;
	pair<int, int> up;

	for (i=0;i<N;i++) X[i] = P[i].x; S = N;
	sort(X,X+N); S = unique(X,X+N) - X;

	sort(P,P+N,cmp);
	for (i=0;i<2*Z;i++) B[i] = make_pair(non,0);
	for (i=0;i<N;i++){
		l = lower_bound(X,X+S,P[i].x-R) - X;
		m = lower_bound(X,X+S,P[i].x) - X;
		r = (upper_bound(X,X+S,P[i].x+R) - X) - 1;

		up = out(l,m);
		if (up.first <= P[i].y + R + D) G[P[i].i].push_back(up.second);
		up = out(m,r);
		if (up.first <= P[i].y + R + D) G[P[i].i].push_back(up.second);

		in(m,make_pair(P[i].y,P[i].i));
	}
}

int main()
{
	int i,x,y,t;

	scanf ("%d %d",&N,&R);
	for (i=0;i<N;i++){
		scanf ("%d %d",&x,&y);
		P[i].x = x; P[i].y = y; P[i].i = i;
		V[i] = x + y + R + R;
	}
	scanf ("%d",&D);

	make(); for (i=0;i<N;i++) P[i].y = -P[i].y;
	make(); for (i=0;i<N;i++) t = -P[i].y, P[i].y = P[i].x, P[i].x = t;
	make(); for (i=0;i<N;i++) P[i].y = -P[i].y;
	make();
	
	queue<int> Q;
	for (i=0;i<N;i++) if (P[i].x == 0 && P[i].y == 0){ Q.push(P[i].i); chk[P[i].i] = 1; break;}
	while (!Q.empty()){
		x = Q.front(); Q.pop();
		if (ANS < V[x]) ANS = V[x];

		for (i=0;i<G[x].size();i++){
			y = G[x][i];

			if (chk[y] == 0){
				Q.push(y); chk[y] = 1;
			}
		}
	}

	printf ("%d\n",ANS);

	return 0;
}

Subtask #1
1.98 / 1.98

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7368 KB Output is correct
2 Correct 1 ms 7368 KB Output is correct
3 Correct 3 ms 7368 KB Output is correct
4 Correct 2 ms 7368 KB Output is correct
5 Correct 1 ms 7368 KB Output is correct
6 Correct 2 ms 7368 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct

Subtask #2
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7368 KB Output is correct
2 Correct 2 ms 7368 KB Output is correct
3 Correct 2 ms 7368 KB Output is correct
4 Correct 4 ms 7368 KB Output is correct
5 Correct 1 ms 7368 KB Output is correct
6 Correct 2 ms 7368 KB Output is correct
7 Correct 2 ms 7368 KB Output is correct

Subtask #3
3.52 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7368 KB Output is correct
2 Correct 2 ms 7368 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 1 ms 7368 KB Output is correct
5 Correct 3 ms 7368 KB Output is correct
6 Correct 18 ms 7368 KB Output is correct
7 Correct 16 ms 7368 KB Output is correct

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7368 KB Output is correct
2 Correct 9 ms 7368 KB Output is correct
3 Correct 7 ms 7368 KB Output is correct
4 Correct 15 ms 7368 KB Output is correct
5 Correct 15 ms 7368 KB Output is correct
6 Correct 18 ms 7632 KB Output is correct
7 Correct 20 ms 7500 KB Output is correct

Subtask #5
4.62 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7368 KB Output is correct
2 Correct 8 ms 7368 KB Output is correct
3 Correct 16 ms 7368 KB Output is correct
4 Correct 15 ms 7368 KB Output is correct
5 Correct 33 ms 7368 KB Output is correct
6 Correct 225 ms 7764 KB Output is correct
7 Correct 229 ms 8028 KB Output is correct

Subtask #6
5.06 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7632 KB Output is correct
2 Correct 80 ms 7632 KB Output is correct
3 Correct 106 ms 8556 KB Output is correct
4 Correct 173 ms 7764 KB Output is correct
5 Correct 252 ms 10140 KB Output is correct
6 Correct 265 ms 10140 KB Output is correct
7 Correct 261 ms 10140 KB Output is correct