Submission #924124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
924124	2024-02-08T13:39:09 Z	pcc	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	1364 ms	229296 KB

lightningrod

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e7+10;
pii arr[mxn];
int N;
vector<int> st;

inline bool cover(pii &a,pii &b){
	if(a.fs < b.fs){
		return a.sc-a.fs<=b.sc-b.fs;
	}
	else return a.sc+a.fs<=b.sc+b.fs;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 0;i<N;i++){
		cin>>arr[i].fs>>arr[i].sc;
	}
	for(int i = 0;i<N;i++){
		while(!st.empty()&&cover(arr[st.back()],arr[i]))st.pop_back();
		if(st.empty()||!cover(arr[i],arr[st.back()]))st.push_back(i);
	}
	cout<<st.size();
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1128 ms	143560 KB	Output is correct
2	Correct	1078 ms	143956 KB	Output is correct
3	Correct	1050 ms	142036 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	28 ms	2652 KB	Output is correct
15	Correct	27 ms	2648 KB	Output is correct
16	Correct	26 ms	3288 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1109 ms	111540 KB	Output is correct
2	Correct	1114 ms	112124 KB	Output is correct
3	Correct	1081 ms	111192 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1128 ms	143560 KB	Output is correct
2	Correct	1078 ms	143956 KB	Output is correct
3	Correct	1050 ms	142036 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	28 ms	2652 KB	Output is correct
18	Correct	27 ms	2648 KB	Output is correct
19	Correct	26 ms	3288 KB	Output is correct
20	Correct	1109 ms	111540 KB	Output is correct
21	Correct	1114 ms	112124 KB	Output is correct
22	Correct	1081 ms	111192 KB	Output is correct
23	Correct	1364 ms	72664 KB	Output is correct
24	Correct	1312 ms	229296 KB	Output is correct
25	Correct	1268 ms	212240 KB	Output is correct