Submission #740495

#	Time	Username	Problem	Language	Result	Execution time	Memory
740495		mzv	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1770 ms	232816 KiB

Main

#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
*/

• Subtask 1: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20