Submission #522759

#	Time	Username	Problem	Language	Result	Execution time	Memory
522759		nhphucqt	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1760 ms	227808 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

	scanf("%d", &numPoint);
	for (int i = 0; i < numPoint; ++i) {
		scanf("%d%d", &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;
		}
	}
	printf("%d", sz);
	return 0;
}

Compilation message (stderr)

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &numPoint);
      |  ~~~~~^~~~~~~~~~~~~~~~~
lightningrod.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d", &points[i].x, &points[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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