Submission #1162

#TimeUsernameProblemLanguageResultExecution timeMemory
1162kriii개구리 (KOI13_frog)C++98
22 / 22
265 ms10140 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...