BZOJ3276 磁力

2023-12-09 03:50

文章标签 磁力 bzoj3276

本文主要是介绍BZOJ3276 磁力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先按照到站的点的距离排个序，然后贪心的每次拿当前范围最大的来找

然后集齐了一组范围递增，可控重量递减的磁铁以后，就可以直接一个个看能不能拿了

但是会TLE，用线段树维护即可

  1 /**************************************************************
  2     Problem: 3276
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:4884 ms
  7     Memory:19364 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12  
 13 using namespace std;
 14 typedef long long ll;
 15 const int N = 250005;
 16  
 17 struct data {
 18     int w, p;
 19     ll d2, r2;
 20      
 21     inline bool operator < (const data &a) const {
 22         return d2 < a.d2;
 23     }
 24 } a[N];
 25  
 26 struct seg_node {
 27     int v;
 28     seg_node *son[2];
 29 } *seg_root, mempool[N << 2], *cnt_seg = mempool, *null;
 30  
 31 int n;
 32 int q[N], H, T;
 33 ll R2;
 34  
 35 inline int lower() {
 36     int l = 1, r = n + 1, mid;
 37     while (l + 1 < r) {
 38         mid = l + r >> 1;
 39         if (a[mid].d2 <= R2) l = mid;
 40         else r = mid;
 41     }
 42     return l;   
 43 }
 44  
 45 inline int read() {
 46     int x = 0, sgn = 1;
 47     char ch = getchar();
 48     while (ch < '0' || '9' < ch) {
 49         if (ch == '-') sgn = -1;
 50         ch = getchar();
 51     }
 52     while ('0' <= ch && ch <= '9') {
 53         x = x * 10 + ch - '0';
 54         ch = getchar();
 55     }
 56     return sgn * x;
 57 }
 58  
 59 #define mid (l + r >> 1)
 60 #define V p -> v
 61 #define Ls p -> son[0]
 62 #define Rs p -> son[1]
 63 inline void new_node(seg_node *&p) {
 64     p = ++cnt_seg;
 65     V = 0, Ls = Rs = null;
 66 }
 67  
 68 inline int get_min(int x, int y) {
 69     if (!x) return y;
 70     if (!y) return x;
 71     return a[x].w < a[y].w ? x : y;
 72 }
 73  
 74 inline void update(seg_node *p) {
 75     V = get_min(Ls -> v, Rs -> v);
 76 }
 77  
 78 void seg_build(seg_node *&p, int l, int r) {
 79     new_node(p);
 80     if (l == r) {
 81         V = l;
 82         return;
 83     }
 84     seg_build(Ls, l, mid), seg_build(Rs, mid + 1, r);
 85     update(p);
 86 }
 87  
 88 void seg_modify(seg_node *p, int l, int r, int pos) {
 89     if (l == r) {
 90         V = 0;
 91         return;
 92     }
 93     if (pos <= mid) seg_modify(Ls, l, mid, pos);
 94     else seg_modify(Rs, mid + 1, r, pos);
 95     update(p);
 96 }
 97  
 98 int seg_query(seg_node *p, int l, int r, int pos) {
 99     if (r <= pos) return V;
100     int res = seg_query(Ls, l, mid, pos);
101     if (pos > mid) res = get_min(res, seg_query(Rs, mid + 1, r, pos));
102     return res;
103 }
104 #undef mid
105 #undef V
106 #undef Ls
107 #undef Rs
108  
109 inline ll sqr(ll x) {
110     return x * x;
111 }
112  
113 int main() {
114     int X, Y, P, x, y, r, i, tmp, pos;
115     null = cnt_seg, null -> son[0] = null -> son[1] = null, null -> v = 0;
116     X = read(), Y = read(), P = read(), R2 = sqr(read()), n = read();
117     for (i = 1; i <= n; ++i) {
118         x = read(), y = read(), a[i].w = read(), a[i].p = read(), r = read();
119         a[i].d2 = sqr(X - x) + sqr(Y - y), a[i].r2 = sqr(r);
120     }
121     sort(a + 1, a + n + 1);
122     seg_build(seg_root, 1, n);
123     while ((pos = lower()) != 0) {
124         tmp = seg_query(seg_root, 1, n, pos);
125         if (!tmp || a[tmp].w > P) break;
126         seg_modify(seg_root, 1, n, tmp);
127         q[++T] = tmp;
128     }
129     while (H <= T) {
130         P = a[q[H]].p, R2 = a[q[H]].r2, ++H;
131         while ((pos = lower()) != 0) {
132             tmp = seg_query(seg_root, 1, n, pos);
133             if (!tmp || a[tmp].w > P) break;
134             seg_modify(seg_root, 1, n, tmp);
135             q[++T] = tmp;
136         }
137     }
138     printf("%d\n", T);
139     return 0;
140 }