Submission #942086

#	Time	Username	Problem	Language	Result	Execution time	Memory
942086		Kiameimon_Welt_Rene	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	74 ms	27064 KiB

Main

#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;
}

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