Submission #999000

#	Time	Username	Problem	Language	Result	Execution time	Memory
999000		Angus_Yeung	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	543 ms	77136 KiB

Main

#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

*/

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31