Submission #942086

#TimeUsernameProblemLanguageResultExecution timeMemory
942086Kiameimon_Welt_ReneAdvertisement 2 (JOI23_ho_t2)C++14
100 / 100
74 ms27064 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
using ll = long long;
using pii = pair<int,int>;
#define elif else if
#define dbg(v)\
    cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;

inline int readInt() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

bool cover(pii a, pii b){
	return abs(a.first-b.first) <= a.second-b.second;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n = readInt();
	pii arr[n];
	for(int i = 0; i < n; i++){
		arr[i].first = readInt();
		arr[i].second = readInt();
	}
  	sort(arr, arr+n);
	vector<pii> v;
	for(int i = 0; i < n; i++){
		while(!v.empty() && cover(arr[i], v.back())) v.pop_back();
		if(v.empty() || (!cover(arr[i], v.back()) && !cover(v.back(), arr[i]))) v.push_back(arr[i]);
	}
	cout << v.size();
	
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...