Submission #941141

#	Time	Username	Problem	Language	Result	Execution time	Memory
941141		dsyz	Advertisement 2 (JOI23_ho_t2)	C++17	10 / 100	204 ms	38700 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	pair<ll,ll> arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	sort(arr,arr + N);
	if(N > 1000){
		set<ll> s;
		for(ll i = 0;i < N;i++){
			s.insert(arr[i].first);
		}
		cout<<s.size()<<'\n';
		return 0;
	}
	vector<ll> covered[N];
	vector<pair<ll,ll> > v;
	for(ll i = 0;i < N;i++){
		for(auto u : v){
			if(arr[i].first - arr[i].second <= u.first){
				covered[i].push_back(u.second);
			}
		}
		v.push_back({arr[i].first - arr[i].second,i});
	}
	/*for(ll i = 0;i < N;i++){
		cout<<"COVERED: ";
		for(auto u : covered[i]){
			cout<<u<<" ";
		}
		cout<<'\n';
	}*/
	bool done[N];
	memset(done,0,sizeof(done));
	ll ans = 0;
	for(ll i = N - 1;i >= 0;i--){
		if(!done[i]){
			ans++;
			done[i] = 1;
			for(auto u : covered[i]){
				done[u] = 1;
			}
		}
	}
	cout<<ans<<'\n';
}

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