제출 #1281859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281859		muhammad-ahmad	Advertisement 2 (JOI23_ho_t2)	C++20	59 / 100	2096 ms	81052 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// #define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 5e5 + 5;
int X[N] = {}, E[N] = {};

signed main(){
	
	ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	
	int n; cin >> n;
	
	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);
	}
	
	map<int, int> vis;
	
	int ans = 0;
	ordered_set idx1, idx2;
	for (auto i : a){
		if (vis[X[i]]) continue;
		
		int it1 = idx1.order_of_key(X[i]);
		int it2 = idx2.order_of_key(-X[i]);
		
		bool F = 0;
		
		if (it1 != 0){
			auto it = idx1.find_by_order(it1 - 1);
			int j = *it;
			j = best[j];
			if (abs(X[j] - X[i]) <= E[j] - E[i]){
				F = 1;
				vis[X[i]] = 1;
			}
		}
		if (it2 != 0){
			auto it = idx2.find_by_order(it2 - 1);
			int j = *it;
			j = best[j * -1];
			if (abs(X[j] - X[i]) <= E[j] - E[i]){
				F = 1;
				vis[X[i]] = 1;
			}
		}
		if (!F) {
			ans++;
			vis[X[i]] = 1;
			idx1.insert(X[i]);
			idx2.insert(-X[i]);
		}
	}
	
	cout << ans << endl;
	
}

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