Submission #988181

#	Time	Username	Problem	Language	Result	Execution time	Memory
988181		dubabuba	Advertisement 2 (JOI23_ho_t2)	C++14	0 / 100	1 ms	2396 KiB

Main

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int LOG = 22;
const int mxn = 1e6 + 3;
const int mod = 1e9 + 7;

int x[mxn], e[mxn], n;

bool operator < (pii a, pii b) { return a.ff < b.ff && a.ss < b.ss; }
bool operator <= (pii a, pii b) { return a.ff <= b.ff && a.ss <= b.ss; }

void solve() {
	cin >> n;
	vector<int> id;
	for(int i = 1; i <= n; i++) {
		cin >> x[i] >> e[i];
		id.push_back(i);
	}

	set<pii> s;
	sort(id.begin(), id.end(), [&](int i, int j) {
		return e[i] > e[j];
	});

	int ans = 0;
	for(int i : id) {
		auto it = s.lower_bound(MP(e[i] - x[i], e[i] + x[i]));
		if(it == s.end()) {
			s.insert(MP(e[i] - x[i], e[i] + x[i]));
			ans++;
		}
	}

	cout << ans << endl;
}

signed main() {
	#ifdef LOCAL
		auto start = chrono::high_resolution_clock::now();
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	signed t = 1; // cin >> t;
	while(t--) solve();
	
	#ifdef LOCAL
		auto end = chrono::high_resolution_clock::now();
		cout << "\n"; for(int i = 0; i <= 20; ++i) cout << '-';
		cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
	#endif
	return 0;
}

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