Submission #828918

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828918	2023-08-17T20:09:54 Z	NK_	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1539 ms	132544 KB

lightningrod

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; scanf("%d", &N);

	vpi stk;
	for(int i = 0; i < N; i++) {
		int x, y; scanf("%d %d", &x, &y);
		int l = x - y, r = x + y;

		while(sz(stk) && l <= stk.back().f && stk.back().s <= r) stk.pop_back();
		if (!sz(stk) || stk.back().s < r) stk.pb(mp(l, r));
	}

	printf("%d", sz(stk));
	exit(0-0);
}					

Compilation message

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

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1483 ms	132472 KB	Output is correct
2	Correct	1465 ms	132544 KB	Output is correct
3	Correct	1441 ms	132404 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	324 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	324 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	324 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	324 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	31 ms	452 KB	Output is correct
15	Correct	32 ms	444 KB	Output is correct
16	Correct	31 ms	1532 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1490 ms	66592 KB	Output is correct
2	Correct	1485 ms	66580 KB	Output is correct
3	Correct	1468 ms	66536 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1483 ms	132472 KB	Output is correct
2	Correct	1465 ms	132544 KB	Output is correct
3	Correct	1441 ms	132404 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	324 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	324 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	320 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	31 ms	452 KB	Output is correct
18	Correct	32 ms	444 KB	Output is correct
19	Correct	31 ms	1532 KB	Output is correct
20	Correct	1490 ms	66592 KB	Output is correct
21	Correct	1485 ms	66580 KB	Output is correct
22	Correct	1468 ms	66536 KB	Output is correct
23	Correct	1539 ms	2136 KB	Output is correct
24	Correct	1461 ms	1796 KB	Output is correct
25	Correct	1470 ms	5800 KB	Output is correct