Submission #1309054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309054		thuhienne	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	452 ms	25312 KiB

Main

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

using ll = long long;

#define re exit(0);

const int maxn = 500009;

int n;
pair <int,int> p[maxn];

bool given[maxn];

priority_queue <pair <int,int>> pq;

//st
pair <int,int> st1[maxn * 4],st2[maxn * 4];

pair <int,int> merge(pair <int,int> a,pair <int,int> b,int type) {
	if (type == 1) {
		return (a.first > b.first ? a : b);
	} else {
		return (a.first < b.first ? a : b);
	}
}

void build(int id,int l,int r) {
	if (l == r) {
		st1[id] = {p[l].first - p[l].second,l};
		st2[id] = {p[l].first + p[l].second,l};
		return;
	}
	int mid = (l + r) >> 1;
	
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	
	st1[id] = merge(st1[id*2],st1[id*2+1],1);
	st2[id] = merge(st2[id*2],st2[id*2+1],2);
}

void obliterate(int id,int l,int r,int pos) {
	if (l > pos || r < pos) return;
	if (l == r) {
		st1[id].first = -2e9 - 100;
		st2[id].first = 2e9 + 100;
		return;
	}
	int mid = (l + r) >> 1;
	
	obliterate(id*2,l,mid,pos);
	obliterate(id*2+1,mid+1,r,pos);
	
	st1[id] = merge(st1[id*2],st1[id*2+1],1);
	st2[id] = merge(st2[id*2],st2[id*2+1],2);
}

pair <int,int> get(int id,int l,int r,int u,int v,int type) {
	if (l > v || r < u) return (type == 1 ? make_pair(-2e9 - 100,0) : make_pair(2e9 + 100,0));
	if (l >= u && r <= v) return (type == 1 ? st1[id] : st2[id]);
	
	int mid = (l + r) >> 1;
	
	return merge(get(id*2,l,mid,u,v,type),get(id*2+1,mid+1,r,u,v,type),type);
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> p[i].first >> p[i].second;
	}
	
	sort(p + 1,p + 1 + n);
	for (int i = 1;i <= n;i++) {
		pq.push({p[i].second,i});
	}
	
	build(1,1,n);
	
	int res = 0;
	while (pq.size()) {
		int chosen = pq.top().second;pq.pop();
		if (given[chosen]) continue;
		
		res++;
		
		given[chosen] = 1;
		obliterate(1,1,n,chosen);
		
		pair <int,int> a = get(1,1,n,1,chosen - 1,1);
		
		while (a.first >= p[chosen].first - p[chosen].second) {
			given[a.second] = 1;
			obliterate(1,1,n,a.second);
			
			a = get(1,1,n,1,chosen - 1,1);
		}
		
		a = get(1,1,n,chosen + 1,n,2);
		
		while (a.first <= p[chosen].first + p[chosen].second) {
			given[a.second] = 1;
			obliterate(1,1,n,a.second);
			
			a = get(1,1,n,chosen + 1,n,2);
		}
		
	}
	
	cout << res;

}

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