Submission #373841

#	Time	Username	Problem	Language	Result	Execution time	Memory
373841		guka415	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	841 ms	262144 KiB

Main

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

• 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