Submission #1162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162		kriii	개구리 (KOI13_frog)	C++98	22 / 22	265 ms	10140 KiB

frog

#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
• Subtask 2: 2.64 / 2.64
• Subtask 3: 3.52 / 3.52
• Subtask 4: 4.18 / 4.18
• Subtask 5: 4.62 / 4.62
• Subtask 6: 5.06 / 5.06