Submission #799382

#	Time	Username	Problem	Language	Result	Execution time	Memory
799382		acatmeowmeow	Advertisement 2 (JOI23_ho_t2)	C++11	100 / 100	1915 ms	715164 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 5e5;
int n, x[N + 5], e[N + 5], indx[N + 5];

struct node {
	int v = -1e18;
	node *lef = nullptr, *rig = nullptr;
	void extend() { if (!lef) lef = new node(), rig = new node(); }
	void update(int tl, int tr, int k, int x) {
		if (tl == tr) v = max(v, x);
		else {
			extend();
			int tm = (tl + tr)/2;
			if (k <= tm) lef->update(tl, tm, k, x);
			else rig->update(tm + 1, tr, k, x);
			v = max(lef->v, rig->v);
		}
	}
	int query(int tl, int tr, int l, int r) {
		if (l > r) return -1e18;
		else if (tl == l && tr == r) return v; 
		else {
			extend();
			int tm = (tl + tr)/2;
			return max(lef->query(tl, tm, l, min(tm, r)), rig->query(tm + 1, tr, max(l, tm + 1), r));
		}
	}
} *low = new node(), *high = new node();

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> x[i] >> e[i];
	iota(indx + 1, indx + n + 1, 1ll);
	sort(indx + 1, indx + n + 1, [&](int a, int b) { return pair<int, int>(e[a], x[a]) > pair<int, int>(e[b], x[b]); });
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int curIndex = indx[i], lowMax = low->query(1, 1e9, 1, x[curIndex]), highMax = high->query(1, 1e9, x[curIndex], 1e9);
		if (e[curIndex] + x[curIndex] > lowMax && e[curIndex] - x[curIndex] > highMax) ans++;
		low->update(1, 1e9, x[curIndex], e[curIndex] + x[curIndex]);
		high->update(1, 1e9, x[curIndex], e[curIndex] - x[curIndex]);
	}	
	cout << ans << '\n';
	return 0;
}

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