#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<int> seg[2], vec[2];
void build(int id, int x, int l, int r)
{
if (l + 1 == r)
{
seg[id][x] = l;
return;
}
int mid = (l + r) >> 1;
build(id, x << 1, l, mid), build(id, x << 1 | 1, mid, r);
if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]])
seg[id][x] = seg[id][x << 1];
else
seg[id][x] = seg[id][x << 1 | 1];
}
int qry(int id, int x, int l, int r, int ql, int qr)
{
// cerr << "ok6\n";
// cerr << id << ' ' << x << ' ' << l << ' ' << ql << ' ' << qr << '\n';
if (ql <= l && r <= qr)
return seg[id][x];
int mid = (l + r) >> 1;
if (qr <= mid)
return qry(id, x << 1, l, mid, ql, qr);
if (ql >= mid)
return qry(id, x << 1 | 1, mid, r, ql, qr);
int retl = qry(id, x << 1, l, mid, ql, qr), retr = qry(id, x << 1 | 1, mid, r, ql, qr);
if (vec[id][retl] <= vec[id][retr])
return retl;
return retr;
}
void upd(int id, int x, int l, int r, int idx)
{
if (l + 1 == r)
{
seg[id][x] = l;
return;
}
int mid = (l + r) >> 1;
if (idx < mid)
upd(id, x << 1, l, mid, idx);
else
upd(id, x << 1 | 1, mid, r, idx);
if (vec[id][seg[id][x << 1]] <= vec[id][seg[id][x << 1 | 1]])
seg[id][x] = seg[id][x << 1];
else
seg[id][x] = seg[id][x << 1 | 1];
}
void solve()
{
int n;
cin >> n;
vector<pii> v(n);
for (auto &[e, x] : v)
cin >> x >> e;
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
vector<int> tmp;
for (auto [e, x] : v)
tmp.emplace_back(x);
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
int c = tmp.size();
vec[0].assign(c, INT_MAX), vec[1] = vec[0];
for (auto [e, x] : v)
{
int id = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
vec[0][id] = min(vec[0][id], e + x);
vec[1][id] = min(vec[1][id], e - x);
}
seg[0].assign(c * 4 + 10, 0), seg[1] = seg[0];
for (int i : {0, 1})
build(i, 1, 0, c);
vector<int> flag(c, 0);
int ans = 0;
cerr << "ok1\n";
for (auto [e, x] : v)
{
int xx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
if (flag[xx])
continue;
cerr << "ok2\n";
++ans;
flag[xx] = 1;
cerr << xx << "...\n";
for (int i : {0, 1})
vec[i][xx] = INT_MAX, upd(i, 1, 0, c, xx);
cerr << "ok3\n";
while (1)
{
int id = qry(0, 1, 0, c, xx, c);
if (vec[0][id] > e + x)
break;
cerr << id << "...\n";
flag[id] = 1;
for (int i : {0, 1})
vec[i][id] = INT_MAX, upd(i, 1, 0, c, id);
}
cerr << "ok4\n";
while (1)
{
int id = qry(1, 1, 0, c, 0, xx);
if (vec[1][id] > e - x)
break;
cerr << id << ' ' << vec[1][id] << "...\n";
cerr << e - x << '\n';
flag[id] = 1;
for (int i : {0, 1})
vec[i][id] = INT_MAX, upd(i, 1, 0, c, id);
}
}
cout << ans << '\n';
}
/*
4
4 2
2 3
3 4
6 5
3
7 10
10 10
7 10
*/
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:60:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | for (auto &[e, x] : v)
| ^
Main.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for (auto [e, x] : v)
| ^
Main.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for (auto [e, x] : v)
| ^
Main.cpp:89:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for (auto [e, x] : v)
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
712 ms |
12060 KB |
Output is correct |
3 |
Correct |
503 ms |
10848 KB |
Output is correct |
4 |
Correct |
145 ms |
15056 KB |
Output is correct |
5 |
Correct |
64 ms |
11468 KB |
Output is correct |
6 |
Execution timed out |
2052 ms |
41944 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
456 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
448 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
456 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
448 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
712 ms |
12060 KB |
Output is correct |
3 |
Correct |
503 ms |
10848 KB |
Output is correct |
4 |
Correct |
145 ms |
15056 KB |
Output is correct |
5 |
Correct |
64 ms |
11468 KB |
Output is correct |
6 |
Execution timed out |
2052 ms |
41944 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |