Submission #1124931

#TimeUsernameProblemLanguageResultExecution timeMemory
1124931hijackedsoulAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
317 ms16536 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main(){
	int n;
	std::cin >> n;
	std::vector <pair<int, int>> arr(n);
	for(int i=0; i<n; i++){
		std::cin >> arr[i].first >> arr[i].second;//{pos, influence}
	}
	sort(arr.begin(), arr.end());
	std::vector<pair<int, int>> ans;
	for(int i=0; i<n; i++){
		int a=arr[i].first, b=arr[i].second;
		while(!ans.empty() && abs(ans.back().first-a) <= abs(ans.back().second-b) && ans.back().second-b<0){
			ans.pop_back();
		}
		if(!ans.empty() && abs(ans.back().first-a) <= abs(ans.back().second-b) && ans.back().second-b>=0){
			continue;
		}
		ans.push_back({a, b});
	}
	std::cout << ans.size();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...