#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 long double llf;
typedef unsigned long long llu;
const int INF = 987654321;
const ll LINF = (ll)1e15;
const int N_ = 100005;
const int R_ = 10005;
const int LF = 131072*2;
namespace DisjointSet {
int grp[N_];
void init() { for(int i = 1; i < N_; i++) grp[i] = i; }
int get(int x) {
int r = x;
while(r != grp[r]) r = grp[r];
while(x != grp[x]) {
int p = grp[x];
grp[x] = r;
x = p;
}
return r;
}
bool merge (int u, int v) {
u = get(u); v = get(v);
grp[u] = v;
return (u != v);
}
};
namespace SegTree {
int Tree[LF+LF];
void init() {
memset(Tree, 0, sizeof Tree);
}
void update (int l, int r, int v) {
l += LF; r += LF;
while(l <= r) {
if((l & 1) == 1) if(Tree[l] < v) Tree[l] = v;
if((r & 1) == 0) if(Tree[r] < v) Tree[r] = v;
l = (l + 1) >> 1;
r = (r - 1) >> 1;
}
}
int get (int x) {
int ret = -1;
for(x += LF; x > 0; x >>= 1) if(ret < Tree[x]) ret = Tree[x];
return ret;
}
};
struct P {
int x, y, n;
P (): x(0), y(0) { }
P (int x, int y): x(x), y(y) { }
P (int x, int y, int n): x(x), y(y), n(n) { }
bool operator < (const P &t) const { return x != t.x ? x < t.x : y < t.y; }
};
int N, R, J;
P D[N_];
P A[N_*5]; int AN;
int *X[N_*5];
bool cmpX (int *a, int *b) {
return *a < *b;
}
int bef[N_*5];
void connect () {
int i, j;
AN = 0;
for(i = 1; i <= N; i++) {
A[++AN] = P(D[i].x, D[i].y, i);
A[++AN] = P(D[i].x, D[i].y+R, i);
A[++AN] = P(D[i].x+R, D[i].y, -i);
A[++AN] = P(D[i].x+R, D[i].y+R, -i);
}
sort(A+1, A+AN+1);
for(i = 1; i <= AN; i++) X[i] = &A[i].y;
sort(X+1, X+AN+1, cmpX);
int last = *X[1]; *X[1] = 1;
for(i = 2, j = 1; i <= AN; i++) {
if(*X[i] != last) ++j;
last = *X[i];
*X[i] = j;
}
SegTree::init();
for(i = 1; i <= AN; i++) {
P &p = A[i];
if(p.n > 0) {
int w = SegTree::get(p.y);
if(w > 0 && abs(p.x - A[w].x) <= J) DisjointSet::merge(abs(A[w].n), p.n);
}else {
if(!bef[p.n]) {
bef[p.n] = p.y;
}else {
SegTree::update(bef[p.n], p.y, i);
bef[p.n] = 0;
}
}
}
}
int main() {
int i, j;
scanf("%d%d", &N, &R);
for(i = 1; i <= N; i++) scanf("%d%d", &D[i].x, &D[i].y);
scanf("%d", &J);
DisjointSet::init();
connect();
for(i = 1; i <= N; i++) swap(D[i].x, D[i].y);
connect();
int f = -1;
int res = 0;
for(i = 1; i <= N; i++) {
if(D[i].x == 0 && D[i].y == 0) f = DisjointSet::get(i);
}
for(i = 1; i <= N; i++) {
if(DisjointSet::get(i) == f) {
res = max(res, D[i].x + D[i].y + R + R);
}
}
printf("%d\n", res);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
16220 KB |
Output is correct |
2 |
Correct |
1 ms |
16220 KB |
Output is correct |
3 |
Correct |
1 ms |
16220 KB |
Output is correct |
4 |
Correct |
0 ms |
16220 KB |
Output is correct |
5 |
Correct |
1 ms |
16220 KB |
Output is correct |
6 |
Correct |
4 ms |
16220 KB |
Output is correct |
7 |
Correct |
2 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
16220 KB |
Output is correct |
2 |
Correct |
2 ms |
16220 KB |
Output is correct |
3 |
Correct |
2 ms |
16220 KB |
Output is correct |
4 |
Correct |
0 ms |
16220 KB |
Output is correct |
5 |
Correct |
2 ms |
16220 KB |
Output is correct |
6 |
Correct |
0 ms |
16220 KB |
Output is correct |
7 |
Correct |
3 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
16220 KB |
Output is correct |
2 |
Correct |
2 ms |
16220 KB |
Output is correct |
3 |
Correct |
1 ms |
16220 KB |
Output is correct |
4 |
Correct |
3 ms |
16220 KB |
Output is correct |
5 |
Correct |
1 ms |
16220 KB |
Output is correct |
6 |
Correct |
16 ms |
16220 KB |
Output is correct |
7 |
Correct |
16 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
16220 KB |
Output is correct |
2 |
Correct |
7 ms |
16220 KB |
Output is correct |
3 |
Correct |
7 ms |
16220 KB |
Output is correct |
4 |
Correct |
16 ms |
16220 KB |
Output is correct |
5 |
Correct |
13 ms |
16220 KB |
Output is correct |
6 |
Correct |
15 ms |
16220 KB |
Output is correct |
7 |
Correct |
15 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16220 KB |
Output is correct |
2 |
Correct |
10 ms |
16220 KB |
Output is correct |
3 |
Correct |
13 ms |
16220 KB |
Output is correct |
4 |
Correct |
14 ms |
16220 KB |
Output is correct |
5 |
Correct |
27 ms |
16220 KB |
Output is correct |
6 |
Correct |
189 ms |
16220 KB |
Output is correct |
7 |
Correct |
189 ms |
16220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
16220 KB |
Output is correct |
2 |
Correct |
75 ms |
16220 KB |
Output is correct |
3 |
Correct |
91 ms |
16220 KB |
Output is correct |
4 |
Correct |
169 ms |
16220 KB |
Output is correct |
5 |
Correct |
199 ms |
16220 KB |
Output is correct |
6 |
Correct |
201 ms |
16220 KB |
Output is correct |
7 |
Correct |
212 ms |
16220 KB |
Output is correct |