oj.uz

Submission #941141

# Submission time Handle Problem Language Result Execution time Memory
941141 2024-03-08T07:59:31 Z dsyz Advertisement 2 (JOI23_ho_t2) C++17
10 / 100
 204 ms 38700 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 47 ms 10256 KB Output is correct
3 Correct 61 ms 10064 KB Output is correct
4 Correct 122 ms 16724 KB Output is correct
5 Correct 58 ms 11660 KB Output is correct
6 Correct 204 ms 38700 KB Output is correct
7 Correct 200 ms 28060 KB Output is correct
8 Correct 129 ms 18116 KB Output is correct
9 Correct 93 ms 17844 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 47 ms 10256 KB Output is correct
3 Correct 61 ms 10064 KB Output is correct
4 Correct 122 ms 16724 KB Output is correct
5 Correct 58 ms 11660 KB Output is correct
6 Correct 204 ms 38700 KB Output is correct
7 Correct 200 ms 28060 KB Output is correct
8 Correct 129 ms 18116 KB Output is correct
9 Correct 93 ms 17844 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -