Submission #988185

#	Time	Username	Problem	Language	Result	Execution time	Memory
988185		dubabuba	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	141 ms	26820 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;
int d[mxn], s[mxn];

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

	sort(id.begin(), id.end(), [&](int i, int j) {
		if(d[i] != d[j]) return d[i] > d[j];
		return s[i] > s[j];
	});

	int en = 0, ans = 0;
	for(int i : id) {
		if(s[i] > en) {
			ans++;
			en = s[i];
		}
	}

	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: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31