Submission #740495

#TimeUsernameProblemLanguageResultExecution timeMemory
740495mzvLightning Rod (NOI18_lightningrod)C++17
100 / 100
1770 ms232816 KiB
#include <bits/stdc++.h>

#define ccd ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'

using namespace std;

/* ------------------------ hi lol ------------------------ */

// author : mzv

ll n,x,y;
stack<pair<ll,ll>> st;
bool useless;

int main() {
	ccd
	cin >> n;
	while (n--) {
		cin >> x >> y;
		useless=0;
		while (st.size()) {
			ll x2=st.top().first;
			ll y2=st.top().second;
			if (x-x2<=y-y2) {
				st.pop(); // bisa ditutup sama point terbaru
			}
			else if (x-x2<=y2-y) { // bisa tertutup sama point lama
				useless=1;
				break;
			}
			else {
				break; // gabsa nutup satu sama lain
			}
		}
		if (useless) continue;
		st.push({x,y});
	}
	cout << st.size() << endl;
}

// bisa pake stack
// soalnya xi <= xi+1
// jd sbnarnya patokan saja sama sblh kirinya gedung terbaru
// kalau point sebuah x,y bisa ditutupi oleh x,y terbaru maka x,y lama dikeluarkan
// jika sebaliknya x,y lama bisa tutupi x,y baru gausah ditambah
// jika sama sama gabisa nutupin maka x,y baru ttp ditambah tp x,y lama tdk diremove
/*
4
1 1
3 2
4 3
5 1
expected ans -> 2
3
3 2
4 3
1 1
expected ans -> 1
5
2 10
3 5
4 9
7 6
9 15
expected ans -> 2
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...