답안 #524998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524998	2022-02-10T12:21:59 Z	blue	IOI 바이러스 (JOI21_fever)	C++17	6 / 100	48 ms	78652 KB

fever

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

using ll = long long;

// #define ll ll;

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";

	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));

	reload(p);
	reload(i);
}

void add_event(ll i, ll p)
{
	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;
		tbv.insert({t, i, p});
	}
}

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

	if(dir[p] == dt)
	{
		// 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));
		if(it != z.begin())
		{
			it--;
			add_event(it->i, p);
			// cerr << "# " << it->i << '\n';
		}

		z = TR_set[TR_label[p]][dl];
		it = z.lower_bound(person(X[p] + inftime[p], -INF));

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

		z = TR_set[TR_label[p]][dl];
		it = z.lower_bound(person(X[p] - inftime[p], +INF));
		if(it != z.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);
		}

		z = TR_set[TR_label[p]][dt];
		it = z.lower_bound(person(X[p] - inftime[p], +INF));
		if(it != z.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);
		}

		z = TR_set[TR_label[p]][dd];
		it = z.lower_bound(person(X[p] + inftime[p], -INF));
		if(it != z.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++)
	{

// 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[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 = 0; 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

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

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	35 ms	78628 KB	Output is correct
3	Correct	35 ms	78608 KB	Output is correct
4	Correct	35 ms	78536 KB	Output is correct
5	Correct	36 ms	78632 KB	Output is correct
6	Correct	37 ms	78540 KB	Output is correct
7	Correct	36 ms	78652 KB	Output is correct
8	Correct	39 ms	78532 KB	Output is correct

Subtask #4

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #6

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #7

0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78576 KB	Output is correct
4	Correct	34 ms	78600 KB	Output is correct
5	Correct	34 ms	78488 KB	Output is correct
6	Correct	34 ms	78560 KB	Output is correct
7	Correct	36 ms	78540 KB	Output is correct
8	Correct	42 ms	78488 KB	Output is correct
9	Correct	36 ms	78480 KB	Output is correct
10	Correct	35 ms	78592 KB	Output is correct
11	Correct	35 ms	78588 KB	Output is correct
12	Correct	34 ms	78596 KB	Output is correct
13	Correct	34 ms	78592 KB	Output is correct
14	Correct	36 ms	78560 KB	Output is correct
15	Correct	35 ms	78540 KB	Output is correct
16	Correct	34 ms	78568 KB	Output is correct
17	Correct	48 ms	78468 KB	Output is correct
18	Correct	44 ms	78540 KB	Output is correct
19	Correct	36 ms	78528 KB	Output is correct
20	Correct	34 ms	78540 KB	Output is correct
21	Correct	41 ms	78520 KB	Output is correct
22	Correct	36 ms	78532 KB	Output is correct
23	Correct	34 ms	78540 KB	Output is correct
24	Correct	35 ms	78532 KB	Output is correct
25	Correct	35 ms	78540 KB	Output is correct
26	Correct	35 ms	78556 KB	Output is correct
27	Correct	43 ms	78476 KB	Output is correct
28	Incorrect	43 ms	78548 KB	Output isn't correct
29	Halted	0 ms	0 KB	-