Submission #1294769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294769		kaiboy	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	133 ms	10148 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int   N = 500000;
const int INF = 0x3f3f3f3f;

int xx[N], ee[N], ii[N], pp[N], qq[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> xx[i] >> ee[i], ii[i] = i;
	sort(ii, ii + n, [] (int i, int j) { return xx[i] != xx[j] ? xx[i] < xx[j] : ee[i] < ee[j]; });
	int n_ = 1;
	for (int h = 1; h < n; h++) {
		int i = ii[h], i_ = ii[n_ - 1];
		if (xx[i] > xx[i_] || ee[i] > ee[i_])
			ii[n_++] = i;
	}
	n = n_;
	for (int p = -INF, h = 0; h < n; h++) {
		int i = ii[h];
		pp[h] = p, p = max(p, xx[i] + ee[i]);
	}
	for (int q = -INF, h = n - 1; h >= 0; h--) {
		int i = ii[h];
		qq[h] = q, q = max(q, ee[i] - xx[i]);
	}
	int ans = 0;
	for (int h = 0; h < n; h++) {
		int i = ii[h];
		if (xx[i] + ee[i] > pp[h] && ee[i] - xx[i] > qq[h])
			ans++;
	}
	cout << ans << '\n';
	return 0;
}

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