Submission #1292558

#TimeUsernameProblemLanguageResultExecution timeMemory
1292558witek_cppAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
831 ms98824 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())

const ll DUZO = 1'000'000'000'000'000;

vector<vector<pair<ll, ll>>> drzewo; //drzewo[0] - to jest drzewo l drzewo[1] to drzewo r

void ustaw(int rd, int ind, pair<ll, ll> val) {
	drzewo[rd][ind] = val;
	ind /= 2;
	while (ind) {
		drzewo[rd][ind] = min(drzewo[rd][ind *2], drzewo[rd][ind * 2 + 1]);
		ind /= 2;
	}
}

pair<ll, ll> zczytaj(int rd, int l, int r) {
	pair<ll, ll> ans = {DUZO, -1};
	ans = min(ans, drzewo[rd][l]);
	ans = min(ans, drzewo[rd][r]);
	while (r > (l + 1)) {
		if (!(l&1)) ans = min(ans, drzewo[rd][l ^ 1]);
		if (r&1) ans = min(ans, drzewo[rd][r ^ 1]);
		l /= 2;
		r /= 2;
	}
	return ans;
}

void solve() {
	int n;
	cin >> n;
	map<ll, ll> maks_e;
	f(i, 0, n) {
		ll x, e;
		cin >> x >> e;
		maks_e[x] = max(maks_e[x], e);
	}
	n = sz(maks_e);
	vector<pair<ll, ll>> a;
	for (pair<ll, ll> ele: maks_e) a.pb(ele);
	sort(all(a));
	vector<int> odw(n, 0);
	priority_queue<pair<ll, ll>> kolejka;
	f(i, 0, n) kolejka.push({a[i].nd, i});
	ll wnk = 0;
	int stala = 1;
	while (n > stala) stala *= 2;
	drzewo.resize(2, vector<pair<ll, ll>>(2 * (stala + 2)));
	f(i, 0, n) {
		drzewo[0][i + stala] = {a[i].nd - a[i].st, i};
		drzewo[1][i + stala] = {a[i].nd + a[i].st, i};
	}
	f(i, n, stala) {
		drzewo[0][i + stala] = {DUZO, -1};
		drzewo[1][i + stala] = {DUZO, -1};
	}
	for (int i = stala - 1; i > 0; i--) {
		f(j, 0, 2) drzewo[j][i] = min(drzewo[j][i * 2], drzewo[j][(i * 2) + 1]);
	}
	while (sz(kolejka)) {
		pair<ll, ll> p1 = kolejka.top();
		kolejka.pop();
		if (odw[p1.nd]) continue;
		odw[p1.nd] = 1;
		wnk++;
		ll wsp = a[p1.nd].nd - a[p1.nd].st;
		while (p1.nd) {
			pair<ll, ll> p2 = zczytaj(0, stala, p1.nd + stala - 1);
			if (p2.st <= wsp) {
				odw[p2.nd] = 1;
				ustaw(0, p2.nd + stala, {DUZO, -1});
			} else {
				break;
			}
		}
		wsp = a[p1.nd].nd + a[p1.nd].st;
		while (p1.nd < (n - 1)) {
			pair<ll, ll> p2 = zczytaj(1, stala + p1.nd + 1, n - 1 + stala);
			if (p2.st <= wsp) {
				odw[p2.nd] = 1;
				ustaw(1, p2.nd + stala, {DUZO, -1});
			} else {
				break;
			}
		}
	}
	cout << wnk << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...