水题笔记_ CH46 A [分块, 翻车]

一轮就滚回来了 文化课快乐

改了改分块的写法 以前的写法…太丑了

懵逼的 题目

传送至 CH

扯淡的 题解

sb分块, 一开始觉得是个三维偏序, 后来发现时间这一维不怎么好搞, 那就大力分块吧…

排序后我们发现, 对于任意一块磁石, 位置符合要求(位置在吸引半径内)的磁石是一个区间, 重量符合要求的磁石也是一个区间

于是我们先按照位置远近排序, 这样我们就相当于在一个区间内找比一个数小的数的个数, 经典的分块问题

然后按照$\sqrt n$的大小分块(其实应该有更好的块大小…但是懒得搞了), 块内按照重量排序, 二分答案(其实有更好的方法), 对于满足条件的石头放入枚举队列中, 并标记为不可再用, 块内重新按照重量排序(其实还有更好的方法), 枚举零散块内的石子, 暴力更新答案

然后…WAWAWAWA…

发现我分块写得实在是太丑了…于是参悟了lydrainbowcat神的代码Emmm…用le, ri数组代替了不靠谱的宏…

然后…TTTTTT…

下载测试点一看woc$10^4$的数据跑了6s多…Emmmm还不如暴力啊woc…

然后发现…woc我怎么整块也块内排序了…这不就$n^2 \lg n$了…

因为一个磁石被选中后就不会再用到了, 改成移动块端点…

然后…WAWA…

INF赋小了…6个f好像会炸?

A了…emmmmmmmm

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define MAXN (250000 + 5)
#define INF (0x7fffffff)
#define LL long long
#define int LL
using namespace std;
struct stone
{
int length, weight, force, range;
stone() {}
stone(int l, int w, int f, int r): length(l), weight(w), force(f), range(r) {}
} b[MAXN];
int n, block, maxb[MAXN], le[MAXN], ri[MAXN];
bool cmp(stone x, stone y)
{ return x.length < y.length; }
bool comp(stone x, stone y)
{ return x.weight < y.weight; }
void init()
{
sort(b + 1, b + n + 1, cmp);
for (int i = 1; i <= n; i += block)
le[++le[0]] = i, ri[++ri[0]] = min(n, i + block - 1), maxb[le[0]] = b[ri[le[0]]].length;
for (int i = 1; i <= le[0]; i++)
sort(b + le[i], b + ri[i] + 1, comp);
}
queue<stone> q;
int ans = 0;
void solve(int fce, int len)
{
int rigk = 0;
for (int i = 1; i <= le[0]; i++)
{
if (maxb[i] > len)
break;
rigk = max(rigk, i);
}
for (int i = 1; i <= rigk; i++)
{
for (; le[i] <= ri[i] && b[le[i]].weight <= fce; le[i]++)
++ans, q.push(b[le[i]]);
}
if (rigk == le[0])
return ;
for (int i = le[rigk + 1]; i <= min(ri[rigk + 1], n); i++)
if (b[i].length <= len && b[i].weight <= fce)
++ans, q.push(b[i]), b[i].weight = INF;
sort(b + le[rigk + 1], b + ri[rigk + 1] + 1, comp);
}
inline int read()
{
int re = 0;
bool f = false;
char x = 0;
while (x < '0' || x > '9')
{
x = getchar();
if (x == '-')
f = true;
}
while (x >= '0' && x <= '9')
{
re = (re << 1) + (re << 3) + x - '0';
x = getchar();
}
return (f ? (-re) : re);
}
main()
{
//#ifndef ONLINE_JUDEG
freopen("in.in", "r", stdin);
// freopen("wa.out", "w", stdout);
//#endif
int x0 = read(), y0 = read(), pl = read(), rl = read();
n = read();
q.push(stone(0, INF, pl, rl * rl));
block = sqrt(n) + 1;
for (int i = 1; i <= n; i++)
{
int srx = read(), sry = read(), srw = read(), srf = read(), srr = read();
b[i] = stone((srx - x0) * (srx - x0) + (sry - y0) * (sry - y0), srw, srf, srr * srr);
}
init();
while (!q.empty())
{
stone dq = q.front();
q.pop();
solve(dq.force, dq.range);
}
printf("%lld", ans);
return 0;
}

/*
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
*/

By …的Cansult