CF1045G-AI robots
题目:
题目描述:
In the last mission, MDCS has successfully shipped $ N $ AI robots to Mars. Before they start exploring, system initialization is required so they are arranged in a line. Every robot can be described with three numbers: position ( $ x_i $ ), radius of sight ( $ r_i $ ) and IQ ( $ q_i $ ).
Since they are intelligent robots, some of them will talk if they see each other. Radius of sight is inclusive, so robot can see other all robots in range $ [x_i - r_i, x_i + r_i] $ . But they don’t walk to talk with anybody, but only with robots who have similar IQ. By similar IQ we mean that their absolute difference isn’t more than $ K $ .
Help us and calculate how many pairs of robots are going to talk with each other, so we can timely update their software and avoid any potential quarrel.
输入格式:
The first line contains two integers, numbers $ N (1 \leq N \leq 10^5) $ and $ K (0 \leq K \leq 20) $ .
Next $ N $ lines contain three numbers each $ x_i, r_i, q_i (0 \leq x_i,r_i,q_i \leq 10^9) $ — position, radius of sight and IQ of every robot respectively.
输出格式:
Output contains only one number — solution to the problem.
样例:
样例输入 1:
1
2
3
4
| 3 2
3 6 1
7 3 10
10 5 8
|
样例输出 1:
思路:
实现:
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
| #include "ybwhead/ios.h"
int n, k;
const int maxn = 2e5 + 10;
struct node
{
int x, l, r, q, len;
} a[maxn];
int tmp[maxn];
long long ans;
int cmp(node a, node b)
{
return a.len > b.len;
}
#define lowbit(x) x &(-x)
void add(int x, int d)
{
for (; x <= n; x += lowbit(x))
tmp[x] += d;
}
int qq(int x)
{
int ans = 0;
for (; x; x -= lowbit(x))
ans += tmp[x];
return ans;
}
int query(int l, int r)
{
return qq(r) - qq(l - 1);
}
int cmp2(node a, node b)
{
return a.q < b.q;
}
void cdq(int l, int r)
{
if (l == r)
return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
int L = l, R = l - 1;
for (int i = mid + 1; i <= r; i++)
{
while (L <= mid && a[i].q - a[L].q > k)
add(a[L].x, -1), ++L;
while (R < mid && a[R + 1].q - a[i].q <= k)
++R, add(a[R].x, 1);
ans += query(a[i].l, a[i].r);
}
for (int i = L; i <= R; i++)
add(a[i].x, -1);
sort(a + l, a + r + 1, cmp2);
}
int main()
{
yin >> n >> k;
for (int i = 1; i <= n; i++)
yin >> a[i].x >> a[i].len >> a[i].q, tmp[i] = a[i].x;
sort(tmp + 1, tmp + n + 1);
int m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
for (int i = 1; i <= n; i++)
a[i].l = lower_bound(tmp + 1, tmp + m + 1, a[i].x - a[i].len) - tmp,
a[i].r = upper_bound(tmp + 1, tmp + m + 1, a[i].x + a[i].len) - tmp - 1,
a[i].x = lower_bound(tmp + 1, tmp + m + 1, a[i].x) - tmp;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
tmp[i] = 0;
cdq(1, n);
yout << ans << endl;
return 0;
}
|