Submission #571065

#	Time	Username	Problem	Language	Result	Execution time	Memory
571065		8e7	IOI Fever (JOI21_fever)	C++17	25 / 100	5073 ms	117336 KiB

fever

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk 
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define x first
#define y second
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e9;
pii a[maxn];
unordered_map<int, set<pii> > horz, vert, ru, rd;
unordered_map<int, set<pii> > t0, t1, t2, t3;
unordered_map<ll, int> mp;
ll h(pii p) {
	return (ll)inf * p.x + p.y;
}
struct pnt{
	pii p;
	int t, d;
	pnt(){t = d = 0;}
	pnt(pii P, int ti, int di){p = P, t = ti, d = di;}
};
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int movru[4][2] = {{1, 1}, {1, 1}, {-1, -1}, {-1, -1}};
int movrd[4][2] = {{1, -1}, {-1, 1}, {-1, 1}, {1, -1}};

int mind[maxn], di[maxn];
bool vis[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i].x >> a[i].y;
		mp[h(a[i])] = i;		
		horz[a[i].y].insert(a[i]);	
		vert[a[i].x].insert(a[i]);	
		ru[a[i].x - a[i].y].insert(a[i]);
		rd[a[i].x + a[i].y].insert(a[i]);
	}
	t0 = horz, t1 = vert, t2 = ru, t3 = rd;	
	int ans = 0;
	for (int init_d = 0;init_d < 4;init_d++) {
		for (int i = 0;i < n;i++) mind[i] = inf, vis[i] = 0;
		mind[0] = 0;
		di[0] = init_d;

		horz = t0, vert = t1, ru = t2, rd = t3;
		queue<pnt> que;
		que.push(pnt(a[0], 0, init_d));
		int cnt = 0;

		auto rm = [&] (pii p) {
			horz[p.x].erase(p);	
			vert[p.y].erase(p);
			ru[p.x - p.y].erase(p);
			rd[p.x + p.y].erase(p);
		};
		pii cur;
		auto cl = [&] (set<pii> &se, auto it, int d, int type) {
			auto iter = se.begin();
			vector<pii> tmp;
			if (type == 0) {
				while (iter != it) {
					tmp.push_back(*iter);
					iter = next(iter);
				}
			} else {
				iter = it;
				while (iter != se.end()) {
					tmp.push_back(*iter);
					iter = next(iter);
				}
			}
			for (auto p:tmp) {
				int ind = mp[h(p)];
				mind[ind] = min(mind[ind], (abs(cur.x - p.x) + abs(cur.y - p.y) + 1) / 2);
				di[ind] = d;
				/*
				rm(p);
				que.push(pnt(p, (abs(cur.x - p.x) + abs(cur.y - p.y) + 1) / 2, d));
				*/
			}
		};
		while (true) {
			int found = -1, best = inf;
			for (int i = 0;i < n;i++) {
				if (!vis[i] && mind[i] < best) {
					best = mind[i];
					found = i;
				}
			}
			if (found == -1) break;
			cur = a[found];
			vis[found] = 1;
			rm(cur);
			cnt++;
			int ti = mind[found], dir = di[found];
			pii pos = {cur.x + mov[dir][0] * ti, cur.y + mov[dir][1] * ti};
			if (dir % 2 == 0) {
				auto it = horz[cur.y].lower_bound(pos);
				if (dir == 0) cl(horz[cur.y], it, 2, 1);
				else cl(horz[cur.y], horz[cur.y].lower_bound(pos), 0, 0);
			} else {
				auto it = vert[cur.x].lower_bound(pos);
				if (dir == 1) cl(vert[cur.x], it, 3, 1);
				else cl(vert[cur.x], vert[cur.x].upper_bound(pos), 1, 0);
			}
			pos = {cur.x + movru[dir][0] * ti, cur.y + movru[dir][1] * ti};
			auto it = ru[cur.x - cur.y].lower_bound(pos);
			auto it2 = ru[cur.x - cur.y].upper_bound(pos);
			if (dir == 0) cl(ru[cur.x-cur.y], it, 3, 1);
			else if (dir == 1) cl(ru[cur.x-cur.y], it, 2, 1);
			else if (dir == 2) cl(ru[cur.x-cur.y], it2, 1, 0);
			else cl(ru[cur.x-cur.y], it2, 0, 0);
			
			pos = {cur.x + movrd[dir][0] * ti, cur.y + movrd[dir][1] * ti};
			it = rd[cur.x + cur.y].lower_bound(pos);
			it2 = rd[cur.x + cur.y].upper_bound(pos);
			if (dir == 0) cl(rd[cur.x + cur.y], it, 1, 1);	
			else if (dir == 1) cl(rd[cur.x + cur.y], it2, 0, 0);	
			else if (dir == 2) cl(rd[cur.x + cur.y], it2, 3, 0);	
			else cl(rd[cur.x + cur.y], it, 2, 1);
		}

		ans = max(ans, cnt);
	}
	cout << ans << "\n";
}

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