Submission #146973

#	Time	Username	Problem	Language	Result	Execution time	Memory
146973		gs14004	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	640 ms	246844 KiB

Main

#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));
}

• 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