7574번: 개구리

https://www.acmicpc.net/problem/7574

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, r, d, res, vis[MXN], dis[MXN];
pair<int, int> tree[MXN * 12];
vector<int> adj[MXN];
struct st {
    int x, y, idx;
}p[MXN];
void update(int h, int l, int r, int gl, int gr, pair<int, int> x) {
    if (r < gl || gr < l) return;
    if (gl <= l&&r <= gr) tree[h] = x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
}
pair<int, int> query(int h, int l, int r, int g) {
    if (r < g || g < l) return{ -1e9,0 };
    if (l == r) return tree[h];
    return max({ tree[h],query(h * 2 + 1, l, (l + r) / 2, g), query(h * 2 + 2, (l + r) / 2 + 1, r, g) });
}
void dfs(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    for (auto it : adj[h]) dfs(it);
    res = max(res, dis[h]);
}
int main() {
    scanf("%d%d", &n, &r);
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        p[i] = { x,y,i };
        dis[i] = x + y;
    }
    scanf("%d", &d);
    for (int i = 0, sz = 0; i < 2; i++) {
        map<int, int> mp;
        for (int j = 0; j < n; j++) {
            swap(p[j].x, p[j].y);
            mp[p[j].y] = mp[p[j].y - r] = mp[p[j].y + r] = 0;
        }
        for (auto &it : mp) it.second = sz++;
        sort(p, p + n, [](st u, st v) {return u.x < v.x; });
        fill(tree, tree + sz * 4, make_pair(-1e9, 0));
        for (int j = 0; j < n; j++) {
            pair<int, int> ps = query(0, 0, sz - 1, mp[p[j].y]), pe = query(0, 0, sz - 1, mp[p[j].y + r]);
            if (p[j].x - ps.first <= r + d) {
                adj[p[j].idx].push_back(ps.second);
                adj[ps.second].push_back(p[j].idx);
            }
            if (p[j].x - pe.first <= r + d) {
                adj[p[j].idx].push_back(pe.second);
                adj[pe.second].push_back(p[j].idx);
            }
            update(0, 0, sz - 1, mp[p[j].y], mp[p[j].y + r], { p[j].x,p[j].idx });
        }
    }
    dfs(min_element(dis, dis + n) - dis);
    printf("%d", res + 2 * r);
    return 0;
}