| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 285773 | cprayer | 개구리 (KOI13_frog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
public class frog {
public static void main(String[] args) {
Problems problems = new Problems();
problems.solve();
}
}
class Problems {
Parser parser = new Parser();
void solve() {
int t = 1;
for (int i = 0; i < t; i++) {
Problem problem = new Problem();
problem.solve(i);
}
}
class Problem {
int N;
int r;
int d;
int[] f;
List<Point> points = new ArrayList<>();
public Problem() {
N = parser.parseInt();
r = parser.parseInt();
points.add(new Point(0, 0, 0));
for (int i = 1; i <= N; i++) {
int x = parser.parseInt();
int y = parser.parseInt();
if (x == 0 && y == 0) {
continue;
}
points.add(new Point(x, y, i));
}
d = parser.parseInt();
f = new int[N + 1];
for (int i = 0; i <= N; i++) {
f[i] = i;
}
}
void solve(int testCase) {
points.sort((o1, o2) -> {
if (o1.y != o2.y) {
return Integer.compare(o1.y, o2.y);
}
return Integer.compare(o1.x, o2.x);
});
merge(points);
for (int i = 0; i < points.size(); i++) {
Point p = points.get(i);
int t = p.x;
p.x = p.y;
p.y = t;
}
points.sort((o1, o2) -> {
if (o1.y != o2.y) {
return Integer.compare(o1.y, o2.y);
}
return Integer.compare(o1.x, o2.x);
});
merge(points);
int ans = 0;
for (int i = 0; i < points.size(); i++) {
Point p = points.get(i);
if (find(p.index) == 0) {
ans = Math.max(ans, p.x + p.y + 2 * r);
}
}
System.out.println(ans);
}
void merge(List<Point> sorted) {
TreeMap<Integer, Point> all = new TreeMap<>();
int leftKey = 0;
int leftVal = sorted.get(0).y;
int length = sorted.size();
for (int rightKey = 0; rightKey < length; rightKey++) {
int rightVal = sorted.get(rightKey).y;
while (leftVal + r < rightVal) {
Point deleted = sorted.get(leftKey);
all.remove(deleted.x, deleted);
leftKey += 1;
leftVal = sorted.get(leftKey).y;
}
Point point = sorted.get(rightKey);
all.put(point.x, point);
Map.Entry<Integer, Point> el = all.floorEntry(point.x - 1);
Map.Entry<Integer, Point> er = all.ceilingEntry(point.x + 1);
if (el != null && point.x <= el.getValue().x + r + d) {
merge(el.getValue().index, point.index);
}
if (er != null && er.getValue().x <= point.x + r + d) {
merge(er.getValue().index, point.index);
}
}
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (a > b) {
int t = a;
a = b;
b = t;
}
f[b] = a;
}
int find(int v) {
return f[v] == v ? v : (f[v] = find(f[v]));
}
class Point {
int x, y, index;
public Point(int x, int y, int index) {
this.x = x;
this.y = y;
this.index = index;
}
}
}
}
class Parser {
private final Iterator<String> stringIterator;
private final Deque<String> inputs;
Parser() {
this(System.in);
}
Parser(InputStream in) {
BufferedReader br = new BufferedReader(new InputStreamReader(in));
stringIterator = br.lines().iterator();
inputs = new ArrayDeque<>();
}
void fill() {
while (inputs.isEmpty()) {
if (!stringIterator.hasNext()) throw new NoSuchElementException();
inputs.addAll(Arrays.asList(stringIterator.next().split(" ")));
while (!inputs.isEmpty() && inputs.getFirst().isEmpty()) {
inputs.removeFirst();
}
}
}
Integer parseInt() {
fill();
if (!inputs.isEmpty()) {
return Integer.parseInt(inputs.pollFirst());
}
throw new NoSuchElementException();
}
Long parseLong() {
fill();
if (!inputs.isEmpty()) {
return Long.parseLong(inputs.pollFirst());
}
throw new NoSuchElementException();
}
Double parseDouble() {
fill();
if (!inputs.isEmpty()) {
return Double.parseDouble(inputs.pollFirst());
}
throw new NoSuchElementException();
}
String parseString() {
fill();
return inputs.removeFirst();
}
}