Submission #1297682

#TimeUsernameProblemLanguageResultExecution timeMemory
1297682Jawad_Akbar_JJAdvertisement 2 (JOI23_ho_t2)C++20
0 / 100
2096 ms16600 KiB
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;
const int N = (1<<19) + 1;
int X[N], E[N], sg1[N<<1], sg2[N<<1];

void insert(int i, int xme, int xpe, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		sg1[cur] = xme;
		sg2[cur] = xpe;
		return;
	}

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, xme, xpe, lc, st, mid);
	insert(i, xme, xpe, rc, mid, en);
	sg1[cur] = max(sg1[lc], sg1[rc]);
	sg2[cur] = min(sg2[lc], sg2[rc]);
}

int get1(int i, int v1, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return st;

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (sg1[lc] >= v1)
		return get1(i, v1, lc, st, mid);
	if (i >= mid)
		return get1(i, v1, rc, mid, en);
	return 0;
}

int get2(int i, int v2, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return st;

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (sg2[rc] <= v2)
		return get2(i, v2, rc, mid, en);
	if (i < mid)
		return get2(i, v2, lc, st, mid);
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	for (int i=1;i<(N<<1);i++)
		sg1[i] = -2.1e9, sg2[i] = 2.1e9;

	int n, Ans = 0, cur;
	cin>>n;


	set<pair<int,int>> st0, st1;
	vector<pair<int,int>> vec(n);
	for (int i=1, x, e;i<=n;i++){
		cin>>x>>e;
		vec[i-1] = {x, e};
	}
	sort(vec.begin(), vec.end());
	for (int i=1;i<=n;i++){
		X[i] = vec[i-1].first, E[i] = vec[i-1].second;

		st1.insert({E[i], i});
		insert(i, X[i] - E[i], X[i] + E[i]);
	}

	while (st1.size() > 0){
		if (st0.size() > 0 and  ((*rbegin(st1)).first <= (*rbegin(st0)).first) ) {
			cur = (*rbegin(st0)).second;
			st0.erase({E[cur], cur});
		}
		else{
			Ans++;
			cur = (*rbegin(st1)).second;
			st1.erase({E[cur], cur});
		}
		// cout<<" "<<Ans<<" "<<cur<<endl;

		while (1){
			int g = get1(cur, X[cur] - E[cur]);
			if (g == 0)
				break;
			insert(g, -2.1e9, 2.1e9);
			// cout<<" - "<<g<<endl;
			st1.erase({E[g], g});
			st0.insert({E[g], g});
		}

		while (1){
			int g = get2(cur, X[cur] + E[cur]);
			if (g == 0)
				break;
			// cout<<" + "<<g<<endl;
			insert(g, -2.1e9, 2.1e9);
			st1.erase({E[g], g});
			st0.insert({E[g], g});
		}

	}

	cout<<Ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...