Submission #1215856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215856		trimkus	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	157 ms	6452 KiB

Main

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


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<array<int, 2>> a(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			cin >> a[i][j];
		}
	}
	sort(begin(a), end(a));
	vector<int> ord(n);
	vector<bool> vis(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		return a[x][1] > a[y][1];
	});
	int res = 0;
	for (auto& i : ord) {
		if (vis[i]) continue;
		//~ cerr << "Now at = " << a[i][0] << " " << a[i][1] << "\n";
		res += 1;
		int sum = a[i][0] + a[i][1];
		for (int j = i; j < n; ++j) {
			if (vis[j] || sum < a[j][0] + a[j][1]) {
				//~ cerr << "Ended at " << a[j][0] << "\n";
				break;
			}
			if (j != i) vis[j] = 1;
		}
		sum = a[i][1] - a[i][0];
		for (int j = i; j >= 0; --j) {
			if (vis[j] || sum < a[j][1] - a[j][0]) {
				//~ cerr << "Ended at " << a[j][0] << "\n";
				break;
			}
			vis[j] = true;
		}
	}
	cout << res << "\n";
}

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