#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];
vector<set<pii>> st[2];
st[0].resize(n);
for (int i = 0; i < n; ++i)
st[0][i].clear();
st[1] = st[0];
for (int i = 0; i < n; ++i)
{
auto [e, x] = v[i];
int id = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
vec[0][id] = min(vec[0][id], e + x);
st[0][id].emplace(e + x, i);
vec[1][id] = min(vec[1][id], e - x);
st[1][id].emplace(e - x, i);
}
seg[0].assign(c * 4 + 10, 0), seg[1] = seg[0];
for (int i : {0, 1})
build(i, 1, 0, c);
vector<int> flag(n, 0);
int ans = 0;
for (int iii = 0; iii < n; ++iii)
{
if (flag[iii])
continue;
flag[iii] = 1;
++ans;
auto [e, x] = v[iii];
for (int j = iii + 1; j < n; ++j)
{
auto [ej, xj] = v[j];
if (e + x >= ej + xj && xj >= x || e - x >= ej - xj && xj <= x)
flag[j] = 1;
}
continue;
int xx = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
// st[0][xx].erase({e + x, iii});
// st[1][xx].erase({e - x, iii});
for (int i : {0, 1})
{
for (auto [vall, ii] : st[i][xx])
flag[ii] = 1;
st[i][xx].clear();
int val = INT_MAX;
if (!st[i][xx].empty())
val = st[i][xx].begin()->first;
vec[i][xx] = INT_MAX, upd(i, 1, 0, c, xx);
}
// cerr << "ok1 " << iii << '\n';
while (1)
{
int id = qry(0, 1, 0, c, xx, c);
if (vec[0][id] > e + x)
break;
auto [val, iiii] = *st[0][id].begin();
// cerr << "ok3 " << iiii << '\n';
flag[iiii] = 1;
auto [eeee, xxxx] = v[iiii];
st[0][id].erase({eeee + xxxx, iiii});
st[1][id].erase({eeee - xxxx, iiii});
for (int i : {0, 1})
{
int val = INT_MAX;
if (!st[i][id].empty())
val = st[i][id].begin()->first;
vec[i][id] = INT_MAX, upd(i, 1, 0, c, id);
}
}
// cerr << "ok2 " << iii << '\n';
if (xx > 0)
{
while (1)
{
int id = qry(1, 1, 0, c, 0, xx);
if (vec[1][id] > e - x)
break;
auto [val, iiii] = *st[1][id].begin();
// cerr << "ok4 " << iiii << '\n';
flag[iiii] = 1;
auto [eeee, xxxx] = v[iiii];
st[0][id].erase({eeee + xxxx, iiii});
st[1][id].erase({eeee - xxxx, iiii});
for (int i : {0, 1})
{
int val = INT_MAX;
if (!st[i][id].empty())
val = st[i][id].begin()->first;
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:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | auto [e, x] = v[i];
| ^
Main.cpp:101:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | auto [e, x] = v[iii];
| ^
Main.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | auto [ej, xj] = v[j];
| ^
Main.cpp:106:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
106 | if (e + x >= ej + xj && xj >= x || e - x >= ej - xj && xj <= x)
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:117:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
117 | for (auto [vall, ii] : st[i][xx])
| ^
Main.cpp:120:17: warning: variable 'val' set but not used [-Wunused-but-set-variable]
120 | int val = INT_MAX;
| ^~~
Main.cpp:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | auto [val, iiii] = *st[0][id].begin();
| ^
Main.cpp:134:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
134 | auto [eeee, xxxx] = v[iiii];
| ^
Main.cpp:139:21: warning: variable 'val' set but not used [-Wunused-but-set-variable]
139 | int val = INT_MAX;
| ^~~
Main.cpp:153:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | auto [val, iiii] = *st[1][id].begin();
| ^
Main.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
156 | auto [eeee, xxxx] = v[iiii];
| ^
Main.cpp:161:25: warning: variable 'val' set but not used [-Wunused-but-set-variable]
161 | int val = INT_MAX;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
2086 ms |
31040 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
1 ms |
604 KB |
Output is correct |
| 21 |
Correct |
1 ms |
604 KB |
Output is correct |
| 22 |
Correct |
1 ms |
604 KB |
Output is correct |
| 23 |
Correct |
1 ms |
604 KB |
Output is correct |
| 24 |
Correct |
2 ms |
708 KB |
Output is correct |
| 25 |
Correct |
1 ms |
604 KB |
Output is correct |
| 26 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
2086 ms |
31040 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
