Submission #373841

#TimeUsernameProblemLanguageResultExecution timeMemory
373841guka415Lightning Rod (NOI18_lightningrod)C++14
100 / 100
841 ms262144 KiB
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

using namespace std;

const int sz = 1e7 + 5;
int n;
int p[sz][2];
int mxx[sz];

inline int readInt() {
	int x = 0; char ch = getchar(); bool s = 1;
	while (ch<'0' || ch>'9') { if (ch == '-')s = 0; ch = getchar(); }
	while (ch >= '0'&&ch <= '9') { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); }
	return s ? x : -x;
}

int main() {
	int xp, yp, ret = 0, prvmny;
	n = readInt();
	for (int i = 0; i < n; i++) {
		xp = readInt();
		yp = readInt();
		p[i][0] = xp + yp;
		p[i][1] = xp - yp;
	}
	mxx[0] = p[0][0];
	for (int i = 1; i < n; i++)
		mxx[i] = (mxx[i - 1] < p[i][0] ? p[i][0] : mxx[i - 1]);
	prvmny = p[n - 1][1];
	for (int i = n - 2; i >= 1; i--) {
		ret += (mxx[i - 1]<p[i][0] && prvmny>p[i][1]);
		prvmny = (prvmny > p[i][1] ? p[i][1] : prvmny);
	}
	ret += (prvmny > p[0][1]);
	ret += (mxx[n - 2] < p[n - 1][0]);
	printf("%d", ret);
	return 0;
}
#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...