磁力块

AcWing-250-磁力块

分析

见《进阶指南》第228页。

实现

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

typedef long long LL;
const int N = 250010, T = 510;
struct node {
    LL d;
    int m;
    int p;
    LL r;
};
int n, t;
node a[N];
int L[T], R[T], max_mass[T];
bool mark[N];

bool cmp1 (const node& a, const node& b) {
    return a.m < b.m;
}
bool cmp2 (const node& a, const node& b) {
    return a.d < b.d;
}
void initialize () {
    sort(a + 1, a + n + 1, cmp1);
    t = sqrt(n);
    for (int i = 1; i <= t; ++ i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * t;
        max_mass[i] = a[R[i]].m;
    }
    if (R[t] < n) {
        ++ t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
        max_mass[t] = a[R[t]].m;
    }
    for (int i = 1; i <= t; ++ i)
        sort(a + L[i], a + R[i] + 1, cmp2);
}
int bfs () {
    int res = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int p = a[cur].p;
        LL r = a[cur].r;

        int ptr = 0;
        for (int i = 1; i <= t && p >= max_mass[i]; ++ i) ptr = i;
        for (int i = 1; i <= ptr; ++ i) {
            while (L[i] <= R[i] && r >= a[L[i]].d) {
                if (mark[L[i]] == false) {
                    q.push(L[i]);
                    ++ res;
                    mark[L[i]] = true;
                }
                ++ L[i];
            }
        }
        if (ptr < t) {
            ++ ptr;
            for (int i = L[ptr]; i <= R[ptr]; ++ i) {
                if (p >= a[i].m && r >= a[i].d && mark[i] == false) {
                    q.push(i);
                    ++ res;
                    mark[i] = true;
                }
            }
        }
    }
    return res;
}

int main () {
    LL x0, y0;
    scanf("%lld%lld%d%lld", &x0, &y0, &a[0].p, &a[0].r);
    a[0].r = a[0].r * a[0].r;
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; ++ i) {
        scanf("%d%d%d%d%lld", &x, &y, &a[i].m, &a[i].p, &a[i].r);
        a[i].d = (x0 - x) * (x0 - x) + (y0 - y) * (y0 - y);
        a[i].r = a[i].r * a[i].r;
    }
    
    initialize();
    printf("%d", bfs());
    return 0;
}