Submission #525027

#	Time	Username	Problem	Language	Result	Execution time	Memory
525027		blue	IOI Fever (JOI21_fever)	C++17	6 / 100	41 ms	78660 KiB

fever

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

using ll = long long;

using mii = map<ll, ll>;
using vi = vector<ll>;
using pii = pair<ll, ll>;
#define sz(x) ll(x.size())

const ll dr = 0;
const ll dt = 1;
const ll dl = 2;
const ll dd = 3;

const ll INF = 2'000'000'001;

ll* X;
ll* Y;

struct person
{
	ll i;
	ll x;
	ll y;

	person(ll I)
	{
		i = I, x = X[I], y = Y[I];
	}

	person(ll X, ll Y)
	{
		x = X, y = Y, i = -1;
	}
};

bool operator < (person A, person B)
{
	if(A.x != B.x) return A.x < B.x;
	else return A.y < B.y;
}


struct event
{
	ll t;

	ll i;
	ll p;
};

bool operator < (event A, event B)
{
	return vi{A.t, A.i, A.p} < vi{B.t, B.i, B.p};
}



const ll mx = 100'000;

vi L_label(mx), T_label(mx), TL_label(mx), TR_label(mx);
mii L_map, T_map, TL_map, TR_map;
set<person> L_set[mx][4], T_set[mx][4], TL_set[mx][4], TR_set[mx][4];
vi dir;
vi visit;

set<event> tbv;

vi inftime;

void activate(event z);
void reload(ll i);


void activate(event z)
{
	ll t = z.t, i = z.i, p = z.p;

	// cerr << "activate " << t << ' ' << i << ' ' << p << "\n";

	

	reload(p);
	reload(i);
}

void add_event(ll i, ll p)
{

	// cerr << "add event " << i << ' ' << p << '\n';

	ll t;
	if(X[i] == X[p]) t = abs(Y[i] - Y[p])/2;
	else if(Y[i] == Y[p]) t = abs(X[i] - X[p])/2;
	else t = abs(X[i] - X[p]);


	if(inftime[i] == -1 || inftime[i] > t)
	{
		inftime[i] = t; 
		visit[i] = 1;


		L_set[L_label[i]][dir[i]].erase(person(i));
		T_set[T_label[i]][dir[i]].erase(person(i));
		TL_set[TL_label[i]][dir[i]].erase(person(i));
		TR_set[TR_label[i]][dir[i]].erase(person(i));

		tbv.insert({t, i, p});
	}
}

void reload(ll p)
{
	// cerr << "\n\n";
	// cerr << "reload " << p << '\n';
	// cerr << "reload " << p << "\n";

	if(dir[p] == dt)
	{
		// cerr << "entered \n";
		// cerr << "hi\n";
		// auto it = T_set[T_label[p]][dd].lower_bound(person(p));
		// if(it != T_set[T_label[p]][dd].begin())
		// {
		// 	it--;
		// 	ll i = it->i;
		// 	add_event(it->i, i);
		// 	T_set[T_label[p]][dd].erase(it);
		// }

		set<person>& z = TL_set[TL_label[p]][dr];



		auto it = z.lower_bound(person(X[p] - inftime[p], INF));

		// cerr << "z = ";
		// for(person xv : z) cerr << xv.x << ' ' << xv.y << " | ";
		// 	cerr << "\n";

		if(it != z.begin())
		{
			it--;
			add_event(it->i, p);
			// cerr << "# " << it->i << '\n';
		}

		set<person>& z2 = TR_set[TR_label[p]][dl];
		it = z2.lower_bound(person(X[p] + inftime[p], -INF));

		// cerr << "z2 = ";
		// for(person xv : z2) cerr << xv.x << ' ' << xv.y << " | ";
		// 	cerr << "\n";

		// cerr << "coords = " << X[0]-Y[0] << ' ' << X[1]-Y[1] << ' ' << X[2]-Y[2] << '\n';

		// cerr << "z = ";
		// for(person q : z) cerr << q.i << " / ";
		// 	cerr << '\n';

		if(it != z2.end())
		{
			add_event(it->i, p);
			// cerr << "#\n";
		}
	}
	else if(dir[p] == dd)
	{
		// cerr << "down p = " << p << '\n';
		set<person>& z = TL_set[TL_label[p]][dl];
		auto it = z.lower_bound(person(X[p] + inftime[p], -INF));

		// cerr << "z = ";
		// for(person q : z) cerr << q.i << " / ";
		// 	cerr << '\n';


		if(it != z.end())
		{
			add_event(it->i, p);
		}

		set<person>& z2 = TR_set[TR_label[p]][dr];
		it = z2.lower_bound(person(X[p] - inftime[p], +INF));
		if(it != z2.begin())
		{
			it--;
			add_event(it->i, p);
		}
	}
	else if(dir[p] == dl)
	{
		set<person>& z = TL_set[TL_label[p]][dd];
		auto it = z.lower_bound(person(X[p] - inftime[p], +INF));
		if(it != z.begin())
		{
			it--;
			add_event(it->i, p);
		}

		set<person>& z2 = TR_set[TR_label[p]][dt];
		it = z2.lower_bound(person(X[p] - inftime[p], +INF));
		if(it != z2.begin())
		{
			it--;
			add_event(it->i, p);
		}
	}
	else if(dir[p] == dr)
	{
		set<person>& z = TL_set[TL_label[p]][dt];
		auto it = z.lower_bound(person(X[p] + inftime[p], -INF));
		if(it != z.end())
		{
			add_event(it->i, p);
		}

		set<person>& z2 = TR_set[TR_label[p]][dd];
		it = z2.lower_bound(person(X[p] + inftime[p], -INF));
		if(it != z2.end())
		{
			add_event(it->i, p);
		}
	}
}



signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	ll N;
	cin >> N;

	X = new ll[N];
	Y = new ll[N];
	for(ll i = 0; i < N; i++) 
	{
		cin >> X[i] >> Y[i];
		X[i] *= 2;
		Y[i] *= 2;
	}

	ll res = 1;

	for(ll i = N-1; i >= 0; i--)
	{
		X[i] -= X[0];
		Y[i] -= Y[0];
	}

	// cerr << X[0] << ' ' << X[1] << ' ' << X[2] << '\n';
	// cerr << Y[0] << ' ' << Y[1] << ' ' << Y[2] << '\n';

	for(ll t = 0; t < 4; t++)
	{
		// cerr << "\n\n\n\n\n\n t = " << t << '\n';


// if(t == 1)
// {
		L_map.clear();
		T_map.clear();
		TL_map.clear();
		TR_map.clear();

		for(ll i = 0; i < N; i++)
		{
			L_map[X[i]] = 0;
			T_map[Y[i]] = 0;
			TL_map[X[i]+Y[i]] = 0;
			TR_map[X[i]-Y[i]] = 0;
		}

		for(mii* mp : {&L_map, &T_map, &TL_map, &TR_map})
		{
			mii& m = *mp;

			ll ct = -1;

			for(auto& z : m)
			{
				z.second = ++ct;
			}
		}


		for(ll i = 0; i < N; i++)
		{
			L_label[i] = L_map[X[i]];
			T_label[i] = T_map[Y[i]];
			TL_label[i] = TL_map[X[i] + Y[i]];
			TR_label[i] = TR_map[X[i] - Y[i]];
		}	

		//0 = right, 1 = top, 2 = left, 3 = down

		dir = vi(N);
		dir[0] = dt;


		for(ll i = 1; i < N; i++)
		{
			if(Y[i] > 0 && X[i]+Y[i] > 0 && Y[i]-X[i] > 0)
				dir[i] = dd;
			else if(Y[i] < 0 && X[i]+Y[i] <= 0 && Y[i]-X[i] <= 0)
				dir[i] = dt;
			else if(X[i] < 0)
				dir[i] = dr;
			else if(X[i] > 0)
				dir[i] = dl;
		}

		// cerr << "dir 3 = " << dir[3] << '\n';

		// cerr << dir[0] << ' ' << dir[1] << ' ' << dir[2] << '\n';


		visit = vi(N, 0);
		inftime = vi(N, -1);

		for(ll i = 0; i < N; i++)
		{
			for(ll d = 0; d < 4; d++)
			{
				L_set[i][d].clear();
				T_set[i][d].clear();
				TL_set[i][d].clear();
				TR_set[i][d].clear();
			}
		}
		
		for(ll i = 1; i < N; i++)
		{
			L_set[L_label[i]][dir[i]].insert(person(i));
			T_set[T_label[i]][dir[i]].insert(person(i));
			TL_set[TL_label[i]][dir[i]].insert(person(i));
			TR_set[TR_label[i]][dir[i]].insert(person(i));
		}





		tbv.insert({0, 0, 0});

		visit[0] = 1;
		inftime[0] = 0;

		while(!tbv.empty())
		{
			event x = *tbv.begin();
			tbv.erase(x);

			activate(x);
		}


		ll curr = 0;
		for(ll i = 0; i < N; i++) curr += visit[i];

		res = max(res, curr);




// }


		for(ll i = 0; i < N; i++)
		{
			ll newX = -Y[i], newY = X[i];
			X[i] = newX;
			Y[i] = newY;
		}
	}

	cout << res << '\n';
}

Compilation message (stderr)

fever.cpp: In function 'void activate(event)':
fever.cpp:82:5: warning: unused variable 't' [-Wunused-variable]
   82 |  ll t = z.t, i = z.i, p = z.p;
      |     ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31