Ch\46a magnetic block (BFS+ block)

N magnets are scattered on a vast field.

The properties of each magnet can be described by a quintuple (x,y,m,p,r), where x,y represent its coordinates, M is the mass of the magnet, p is the magnetic force, and r is the radius of attraction.

If the distance between magnet A and magnet B is not greater than the attraction radius of magnet A, and the mass of magnet B is not greater than the magnetic force of magnet A, then A can attract B.

Xiaoqujiu came to the (x0,y0)(x0,y0) of the field with his own magnet L. we can regard the coordinates of the magnet l as (x0,y0)(x0,y0).

Hold the magnet L in your hand and keep it still. All magnets that can be attracted by l will be attracted.

At each moment, he can choose to replace any magnet he has obtained (of course, it can also be the L magnet he originally carried) to attract more magnets at (x0,y0)(x0,y0).

Xiaoqu wants to know how many magnets he can get at most?

Input format

The five integers x0,y0,pL,rL,Nx0,y0,pL,rL,N in the first line represent the location of the small wine taking, the magnetic force of the magnet L, the attraction radius and the number of magnets scattered on the field.

The next N lines each contain five integers x,y,m,p,r, which describe the properties of a magnet.

Output format

An integer is output to indicate the maximum number of scattered magnets that can be obtained (excluding the initially carried magnet L).

Data range

1≤N≤2500001≤N≤250000,
−109≤x,y≤109−109≤x,y≤109,
1≤m,p,r≤1091≤m,p,r≤109

Input example:

0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9

Output example:

3

The blue book explains it clearly. It is clever to maintain the left end point of the block in time. There are detailed explanations in the notes.
#include <bits/stdc++.h>
#define SIZE 250005
using namespace std;
int x0, y00, pl, rl, N, ans = 0;
int L[SIZE], R[SIZE], pos[SIZE], t;
bool vis[SIZE] = {0};
struct Stone{
    int x, y, m, p, r;
    double dis;//distance 
} s[SIZE];
double calc(Stone a, Stone b){
    return sqrt(1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b. y) * (a.y - b.y));
}
bool cmp1(Stone a, Stone b){
    return a.m < b.m;
}
bool cmp2(Stone a, Stone b){
    return a.dis < b.dis;
}
queue<Stone> q;
void BFS(){
    int m = 0;
    q.push(Stone{x0, y00, m, pl, rl});
    while(q.size()){
        Stone temp = q.front();
        q.pop();
        for(int i = 1; i <= t; i++){//Traversal block 
            int cnt = 0, j;//cnt Is the number that the mass in the current block is greater than the gravity of the current handheld magnet 
            for(j = L[i]; j <= R[i]; j++){//Traversal within block 
                if(s[j].m > temp.p) cnt++;//adopt cnt Variable to determine whether the mass of the magnet in the current block is less than the gravity of the handheld magnet, so as to determine whether it is a "corner block" 
                else{
                    if(s[j].dis <= 1ll * temp.r){//First judge the distance 
                        if(!vis[j]){//Second, judge whether you have visited. For the "corner block" of a cycle, the magnets contained in it may have entered the queue, but the end point of the interval has not changed. Therefore, additional judgment is required 
                            ans++;
                              vis[j] = 1;
                              q.push(s[j]);
                         }
                    }
                    else break;//Because the blocks are sorted by distance, if it is greater than, the cycle of the current block will be ended directly 
                }
            }
            if(!cnt) L[i] = j;//The endpoint is updated only when the quality is all less than (indicating that the current block is not a corner block) 
            else break;//There is a magnet with a mass greater than the gravity of the hand-held magnet in the current block, which indicates that it is a corner block, and the cycle is ended directly 
        }
    }
}
int main(){
    cin >> x0 >> y00 >> pl >> rl >> N;
    for(int i = 1; i <= N; i++) {
        scanf("%d%d%d%d%d", &s[i].x, &s[i].y, &s[i].m, &s[i].p, &s[i].r);
        s[i].dis = calc(s[i], Stone{x0, y00, 0, 0, 0});
    }
    sort(s + 1, s + N + 1, cmp1);//Overall sorted by quality 
    //Conventional block pretreatment 
    t = sqrt(N);
    for(int i = 1; i <= t; i++){
        L[i] = (i - 1) * sqrt(N) + 1;
        R[i] = i * sqrt(N);
    }
    if(R[t] < N) t++, L[t] = R[t - 1] + 1, R[t] = N; 
    for(int i = 1; i <= t; i++){
        for(int j = L[i]; j <= R[i]; j++){
            pos[j] = i;
        }
    }
    for(int i = 1; i <= t; i++){
        sort(s + L[i], s + R[i] + 1, cmp2);//Sort by distance within a block 
    }
    BFS();
    cout << ans;
}

 

 

Tags: partitioning

Posted by kiranoleti on Mon, 30 May 2022 21:23:32 +0530