Submission #1281890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281890		muhammad-ahmad	Advertisement 2 (JOI23_ho_t2)	C++20	0 / 100	433 ms	20200 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	int n; cin >> n;
	int X[n + 1] = {}, E[n + 1] = {};
	
	map<int, int> ma, best; 
	
	for (int i = 1; i <= n; i++){
		cin >> X[i] >> E[i];
		ma[X[i]] = max(ma[X[i]], E[i]);
	}
	
	for (int i = 1; i <= n; i++){
		if (ma[X[i]] == E[i]) best[X[i]] = i;
	}
	
	map<int, vector<int>> idx;
	
	vector<int> iter;
	
	for (int i = 1; i <= n; i++){
		if (idx[E[i]].size() == 0) iter.push_back(E[i]);
		idx[E[i]].push_back(i);
	}
	
	sort(iter.rbegin(), iter.rend());
	vector<int> a;
	for (auto i : iter){
		for (auto j : idx[i]) a.push_back(j);
	}
	
	int ans = 0;
	int vis[n + 1] = {};
	for (auto i : a){
		if (vis[i]) continue;
		ans++;
		vis[i] = 1;
		int idx = i - 1;
		while (idx > 0 && vis[idx] == 0){
			if (abs(X[i] - X[idx]) <= E[i] - E[idx]){
				vis[idx] = 2;
			}
			idx--;
		}
		idx = i + 1;
		while (idx <= n && vis[idx] == 0){
			if (abs(X[i] - X[idx]) <= E[i] - E[idx]){
				vis[idx] = 2;
			}
			idx++;
		}
	}
	
	// for (int i = 1; i <= n; i++) cout << vis[i] << ' ';
	// cout << endl;
	
	cout << ans << endl;
	
}

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