Submission #999000

#TimeUsernameProblemLanguageResultExecution timeMemory
999000Angus_YeungAdvertisement 2 (JOI23_ho_t2)C++17
100 / 100
543 ms77136 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...