Submission #522757

#	Time	Username	Problem	Language	Result	Execution time	Memory
522757		nhphucqt	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2031 ms	246288 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct Point {
	int x, y;
	Point() {}
	Point(int _x, int _y) {
		x = _x; y = _y;
	}
};

const int N = 1e7+7;
int numPoint, sz;
Point points[N], st[N];

bool inside(const Point &a, const Point &b) { // check if a is inside b
	return abs(b.x - a.x) <= b.y - a.y;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	#ifdef NHPHUCQT
	freopen("demo.inp", "r", stdin);
	freopen("demo.out", "w", stdout);
	#endif // NHPHUCQT

	cin >> numPoint;
	for (int i = 0; i < numPoint; ++i) {
		cin >> points[i].x >> points[i].y;
	}
	for (int i = 0, cnt = 0, maxs = 0; i < numPoint; ++i) {
		cnt++; maxs = max(maxs, points[i].y);
		if (i + 1 == numPoint || points[i].x != points[i+1].x) {
			while (sz > 0 && inside(st[sz-1], Point(points[i].x, maxs))) {
				sz--;
			}
			if (sz == 0 || !inside(Point(points[i].x, maxs), st[sz-1])) {
				st[sz++] = points[i];
			}
			cnt = maxs = 0;
		}
	}
	cout << sz;
	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: 0 / 20