Submission #739806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739806	2023-05-11T10:28:19 Z	MODDI	Lightning Rod (NOI18_lightningrod)	C++17	40 / 100	2000 ms	184236 KB

lightningrod

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vector<pii> arr;
int main(){
	cin>>n;
	arr.resize(n);
	priority_queue<pii> pq;
	for(int i = 0; i < n; i++){
		cin>>arr[i].first>>arr[i].second;
		pq.push(mp(arr[i].second, i));
	}
	bool vis[n];
	memset(vis, false, sizeof vis);
	int ans = 0;
	while(!pq.empty()){
		pii here = pq.top();
		pq.pop();
		if(vis[here.second])	continue;
		else{
			ans++;
			for(int i = here.second + 1; i < n; i++){
				if(vis[i])	continue;
				else if(abs(arr[here.second].first - arr[i].first) <= here.first - arr[i].second){
					vis[i] = true;
				}
				else
					continue;
			}
			for(int i = here.second-1; i >= 0; i--){
				if(vis[i])	continue;
				else if(abs(arr[here.second].first - arr[i].first) <= here.first - arr[i].second){
					vis[i] = true;
				}
				else
					continue;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2085 ms	153812 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

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	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 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	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 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	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	2 ms	312 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct

Subtask #5

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	296 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	2 ms	312 KB	Output is correct
12	Correct	4 ms	364 KB	Output is correct
13	Correct	7 ms	340 KB	Output is correct
14	Correct	213 ms	7072 KB	Output is correct
15	Correct	262 ms	7040 KB	Output is correct
16	Execution timed out	2073 ms	6128 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2057 ms	184236 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2085 ms	153812 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-