Submission #146973

#TimeUsernameProblemLanguageResultExecution timeMemory
146973gs14004Lightning Rod (NOI18_lightningrod)C++17
100 / 100
640 ms246844 KiB
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 10000005;

static char buf[1 << 19]; // size : any number geq than 1024
static int idx = 0;
static int bytes = 0;
static inline int _read() {
	if (!bytes || idx == bytes) {
		bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
		idx = 0;
	}
	return buf[idx++];
}
static inline int _readInt() {
	int x = 0, s = 1;
	int c = _read();
	while (c <= 32) c = _read();
	if (c == '-') s = -1, c = _read();
	while (c > 32) x = 10 * x + (c - '0'), c = _read();
	if (s < 0) x = -x;
	return x;
}


int n;
pi a[MAXN];
vector<int> stk;

bool in(int x, int y){
	return a[x].first - a[x].second <= a[y].first - a[y].second &&
	a[y].first + a[y].second <= a[x].first + a[x].second;
}

int main(){
	n = _readInt();
	for(int i=0; i<n; i++){
		a[i].first = _readInt();
		a[i].second = _readInt();
		if(stk.empty()) stk.push_back(i);
		else{
			if(in(stk.back(), i)) continue;
			while(!stk.empty() && in(i, stk.back())) stk.pop_back();
			stk.push_back(i);
		}
	}
	printf("%d\n", sz(stk));
}
#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...