이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define x first
#define e second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;
ll n, x, e, k, ans;
pii a[500010];
bool vis[500010];
map<ll, ll> mp;
set<pii> q;
int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x >> e;
mp[x] = max(mp[x], e);
}
k = 0;
for (auto i: mp) {
k++;
a[k] = i;
vis[k] = 0;
}
while (q.size()) q.erase(q.begin());
for (int i = 1; i <= k; i++) {
while (q.size() && a[i].x - a[i].e <= q.rbegin()->first) {
vis[q.rbegin()->second] = 1;
q.erase(*q.rbegin());
}
q.insert({a[i].x - a[i].e, i});
}
while (q.size()) q.erase(q.begin());
for (int i = k; i >= 1; i--) {
while (q.size() && a[i].x + a[i].e >= q.begin()->first) {
vis[q.begin()->second] = 1;
q.erase(*q.begin());
}
q.insert({a[i].x + a[i].e, i});
}
ans = 0;
for (int i = 1; i <= k; i++) {
ans += !vis[i];
}
cout << ans << "\n";
return 0;
}
/*
xi - ei <= xj - ej
xi + ei >= xj + ej
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |