Submission #503485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503485	2022-01-08T07:31:47 Z	mohit_joshi	Lightning Rod (NOI18_lightningrod)	C++14	40 / 100	2000 ms	262148 KB

lightningrod

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std ;
const int N = 1e5 + 5;
int main ()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n ;
	cin >> n ;
	vector<pair<ll, ll>>v;
	set<pair<ll, ll>, greater<pair<ll, ll>>>s;
	for (int i = 0; i < n; i++)
	{
		ll x, y ;
		cin >> x >> y ;
		v.pb({x, y});
		s.insert({y, x});
	}
	int count = 0;
	while (!s.empty())
	{
		count++;
		pair<ll, ll>temp = (*(s.begin()));
		ll y = temp.ff;
		ll x = temp.ss;
		s.erase(*(s.begin()));
		for (int i = 0; i < n; i++)
		{
			ll x1 = v[i].ff;
			ll y1 = v[i].ss;
			if (abs(x - x1) <= y - y1)
			{
				auto it = s.find({y1, x1});
				if (it != s.end())
				{
					s.erase(it);
				}
			}
		}
	}
	cout << count << "\n";
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1375 ms	262144 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

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

Subtask #5

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	308 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	4 ms	460 KB	Output is correct
13	Correct	6 ms	504 KB	Output is correct
14	Correct	678 ms	18344 KB	Output is correct
15	Correct	461 ms	18844 KB	Output is correct
16	Execution timed out	2084 ms	17320 KB	Time limit exceeded

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1097 ms	262148 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1375 ms	262144 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-