제출 #917689

#제출 시각아이디문제언어결과실행 시간메모리
917689happypotatoAdvertisement 2 (JOI23_ho_t2)C++17
100 / 100
133 ms18380 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
bool contain(pii lhs, pii rhs) {
	return abs(lhs.ff - rhs.ff) <= (lhs.ss - rhs.ss);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n; cin >> n;
	pii a[n];
	for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].ss;
	sort(a, a + n);
	
	vector<pii> sel;
	for (int i = 0; i < n; i++) {
		while (!sel.empty()) {
			if (contain(a[i], sel.back())) sel.pop_back();
			else break;
		}
		if (sel.empty() || !contain(sel.back(), a[i])) {
			sel.pb(a[i]);
		}
	}

	cout << sel.size() << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...