Submission #1322318

#TimeUsernameProblemLanguageResultExecution timeMemory
1322318limitsAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
342 ms14652 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << '\n';
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;

struct ST {
	vi tr;
	int N;

	ST(int n) {
		for (N=1; N<n; N*=2);
		tr.assign(2*N, 2e9);
	}

	#define m (l+r)/2
	int query(int ql, int qr, int v, int l, int r) {
		if (qr < l || r < ql) return 2e9;
		if (ql <= l && r <= qr) return tr[v];
		return min(query(ql, qr, 2*v, l, m), query(ql, qr, 2*v+1, m+1, r));
	}
	void upd(int q, int x, int v, int l, int r) {
		if (q < l || r < q) return;
		if (l == r) {
			tr[v] = min(tr[v], x);
			return;
		}
		upd(q, x, 2*v, l, m);
		upd(q, x, 2*v+1, m+1, r);
		tr[v] = min(tr[2*v], tr[2*v+1]);
	}
	#undef m
	int query(int ql, int qr) { return query(ql, qr, 1, 0, N-1); }
	void upd(int q, int x) { upd(q, x, 1, 0, N-1); }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	V<pi> ppl(N);
	vi xs;
	for (auto &[e, x]: ppl) {
		cin >> x >> e;
		xs.pb(x);
	}
	sort(all(xs));
	xs.erase(unique(all(xs)), end(xs));
	sort(all(ppl), greater<>());

	ST st1(xs.size()), st2(xs.size());

	int cnt = 0;
	for (auto &[e, x]: ppl) {
		int i = lower_bound(all(xs), x) - begin(xs);
		if (st1.query(i, xs.size()-1) <= x - e || st2.query(0, i) <= -(e + x)) continue;
		++cnt;
		st1.upd(i, x - e);
		st2.upd(i, -e -x);
	}
	ctn(cnt);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...