Submission #146972

#	Time	Username	Problem	Language	Result	Execution time	Memory
146972		gs14004	Lightning Rod (NOI18_lightningrod)	C++17	66 / 100	2059 ms	229448 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;

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(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first,&a[i].second);
		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));
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
lightningrod.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first,&a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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