Submission #639085

#	Time	Username	Problem	Language	Result	Execution time	Memory
639085		luanaamorim	Wish (LMIO19_noras)	C++14	100 / 100	124 ms	11416 KiB

noras

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#define dbug(x) cout << (#x) << " -> " << x << endl
#define ll long long
#define INF (1e9)
#define MAX (int) (2e5 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

ll n, r, a, b, deltax, deltay, resp, qtd;
vector<pair<ll, ll> > v;
priority_queue<ll, vector<ll>, greater<ll> > pq;

pair<ll, ll> tempo(double x, double y, double dx, double dy)
{
	int ok = 0;
	double a = (dx*dx) + (dy*dy);
	double b = (2*dx*x) + (2*dy*y);
	double c = (x*x) + (y*y) - (r*r);
	// dbug(a);
	// dbug(b);
	// dbug(c);
	double delta = (b*b) - (4*a*c);
	// dbug(delta);
	if (delta<0) return {INF, INF};
	double r1 = (-b - sqrt(delta)) / (2*a);
	double r2 = (-b + sqrt(delta)) / (2*a);
	// dbug(delta);
	// dbug(r1);
	// dbug(r2);

	// dbug(sqrt(delta));
	for (ll i = max((double)0, r1-2); i <= r1+2; i++)
	{
		ll px = x + (dx*i);
		ll py = y + (dy*i);
		// dbug(px);
		// dbug(py);
		if ((px*px) + (py*py) <= r*r) 
		{
			// dbug(r1);
			ok = 1;
			r1 = i;
			break;
		}
	}

	for (ll i = r2+2; i >= max((double)0, r2-2); i--)
	{
		ll px = x + (dx*i);
		ll py = y + (dy*i);
		if ((px*px) + (py*py) <= r*r) 
		{
			ok = 1;
			r2 = i;
			break;
		}
	}

	if (!ok) return {INF, INF};
	return {max(0LL, (ll)r1), (ll)r2};
}

int main()
{_
	cin >> n >> r;
	for (int i = 1; i <= n; i++)
	{
		cin >> a >> b >> deltax >> deltay;
		deltax -= a;
		deltay -= b;
		// dbug(deltax);
		// dbug(deltay);
		v.push_back(tempo(a, b, deltax, deltay));
	}

	sort(all(v));
	for (auto[l, r] : v)
	{
		if (l == INF && r == INF) break;
		// cout << l << ' ' << r << endl;
		while (!pq.empty() && pq.top() < l) pq.pop(), qtd--;
		qtd++;
		resp = max(resp, qtd);
		pq.push(r);
	}

	cout << resp << endl;

}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:98:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |  for (auto[l, r] : v)
      |           ^

• Subtask 1: 23 / 23
• Subtask 2: 23 / 23
• Subtask 3: 15 / 15
• Subtask 4: 32 / 32
• Subtask 5: 7 / 7