제출 #963899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963899		TranGiaHuy1508	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	482 ms	35652 KiB

Main

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int inf = 2e9;

struct Segtree {
	vector<int> tree;
	int _n;

	Segtree() {}
	Segtree(int N): tree(4 * N, -inf), _n(N) {}

	void update(int pos, int val){
		update(1, 0, _n - 1, pos, val);
	}

	void update(int i, int l, int r, int pos, int val){
		if (l == pos && r == pos){
			tree[i] = val;
			return;
		}

		int mid = (l + r) >> 1;
		if (pos <= mid) update(i<<1, l, mid, pos, val);
		else update(i<<1|1, mid+1, r, pos, val);
		tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}

	int get(int tl, int tr){
		return get(1, 0, _n - 1, tl, tr);
	}

	int get(int i, int l, int r, int tl, int tr){
		if (tl <= l && r <= tr) return tree[i];
		if (tl > r || tr < l) return -inf;

		int mid = (l + r) >> 1;
		int resl = get(i<<1, l, mid, tl, tr);
		int resr = get(i<<1|1, mid+1, r, tl, tr);
		return max(resl, resr);
	}
};

int n;
vector<int> X, E;
vector<int> order, pos;

void main_program(){
	cin >> n;

	X.resize(n);
	E.resize(n);
	order.resize(n);
	pos.resize(n);

	for (int i = 0; i < n; i++){
		cin >> X[i] >> E[i];
	}

	iota(order.begin(), order.end(), 0);
	sort(order.begin(), order.end(), [&](int x, int y){
		return X[x] < X[y];
	});

	for (int i = 0; i < n; i++) pos[order[i]] = i;

	vector<int> vec(n);
	iota(vec.begin(), vec.end(), 0);
	sort(vec.begin(), vec.end(), [&](int x, int y){
		return E[x] > E[y];
	});

	int res = 0;
	Segtree st_delta(n), st_sum(n);

	for (auto idx: vec){
		bool alr = false;
		if (st_delta.get(pos[idx], n-1) >= E[idx] - X[idx]) alr = true;
		if (st_sum.get(0, pos[idx]) >= E[idx] + X[idx]) alr = true;

		if (alr) continue;

		res++;
		st_delta.update(pos[idx], E[idx] - X[idx]);
		st_sum.update(pos[idx], E[idx] + X[idx]);
	}

	cout << res << "\n";
}

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