Submission #676478

#	Time	Username	Problem	Language	Result	Execution time	Memory
676478		penguin133	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	490 ms	245692 KiB

Main

#include <bits/stdc++.h>
using namespace std;

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

int X[10000000], Y[10000000];

int main(){
	//int N;
	//cin >> N;
	int N = readInt();
	for(int i = 0; i < N; i++) {
		//cin >> X[i];
		//cin >> Y[i];
		X[i] = readInt();
		Y[i] = readInt();
		// write code here
	}
	int cnt = N;
	stack<pair<int, int> >s;
	for(int i=0; i<N;i++){
		int f = 1;
		while(!s.empty()){
			int a = s.top().first;
			int b = s.top().second;
			if(X[i] - a <= b - Y[i]){
				f = 0;
				break;
			}
			else if(X[i] - a <= Y[i] - b){
				s.pop();
			}
			else{
				break;
			}
		}
		if(f == 1){
			s.push(make_pair(X[i] , Y[i]));
		}
	}
	cout << s.size();
	// write code here
	return 0;
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:28:6: warning: unused variable 'cnt' [-Wunused-variable]
   28 |  int cnt = N;
      |      ^~~

• 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