Submission #503485

#	Time	Username	Problem	Language	Result	Execution time	Memory
503485		mohit_joshi	Lightning Rod (NOI18_lightningrod)	C++14	40 / 100	2084 ms	262148 KiB

Main

#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
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20