Submission #427857

#	Time	Username	Problem	Language	Result	Execution time	Memory
427857		amoo_safar	IOI Fever (JOI21_fever)	C++17	69 / 100	3074 ms	524292 KiB

fever

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
#define int long long

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int Inf = 2'000'000'010;


int n;
int x[N], y[N];
int dir[N];
pii vec[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

set< pair<int, int> > st; // time, id
int mk[N];

set<pair<int, int> > vis;

int Collision(int a, int b){
	if(x[a] > x[b]) swap(a, b);
	if(x[a] == x[b]){
		if(y[a] > y[b]) swap(a, b);
		if(dir[a] == 3 && dir[b] == 1)
			return abs(y[a] - y[b]) / 2;
		return Inf;
	}

	if(y[a] == y[b]){
		// if(y[a] > y[b]) swap(a, b);
		if(dir[a] == 0 && dir[b] == 2)
			return abs(x[a] - x[b]) / 2;
		return Inf;
	}

	int dp_a = x[a] + y[a];
	int dp_b = x[b] + y[b];
	int dn_a = x[a] - y[a];
	int dn_b = x[b] - y[b];
	if(dp_a != dp_b && dn_a != dn_b)
		return Inf;
	int d = abs(x[a] - x[b]);
	if(dp_a == dp_b){
		if((dir[a] == 0 && dir[b] == 3) || (dir[a] == 1 && dir[b] == 2))
			return d;
		return Inf;
	} 
	if((dir[a] == 0 && dir[b] == 1) || (dir[a] == 3 && dir[b] == 2))
		return d;
	return Inf;
}

int dis[N];

struct Line {
	int spd = 1, sz;
	vector<pii> Stop, Move;
	vector<pii> ans, mn;
	vector<int> lz;
	void Apply(int id, int x){
		// debug(x);
		ans[id] = min(ans[id], pii(mn[id].F + x, mn[id].S));
		lz[id] = min(lz[id], x);
	}
	void Shift(int id){
		if(lz[id] != 1){
			Apply(id << 1, lz[id]);
			Apply(id << 1 | 1, lz[id]);
		}
		lz[id] = 1;
	}
	void Build(int id, int L, int R){
		lz[id] = 1;
		if(L + 1 == R){
			ans[id] = {Inf, Stop[L].S};
			mn[id] = Stop[L];
			return ;
		}
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
		ans[id]=min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1],  mn[id << 1 | 1]);
	}
	void Off(int id, int idx, int L, int R){
		if(L + 1 == R){
			mn[id].F = 10 * Inf;
			ans[id] = mn[id];
			return ;
		}
		int mid = (L + R) >> 1;
		Shift(id);
		if(idx < mid)
			Off(id << 1, idx, L, mid);
		else
			Off(id<<1|1, idx, mid, R);
		ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);	
	}
	void Add(int id, int l, int r, int x, int L, int R){
		// for(int i = l; i < r; i++)
		// return ;
		if(r <= L || R <= l) return ;
		if(l <= L && R <= r){
			Apply(id, x);
			return ;
		}
		int mid = (L + R) >> 1;
		Shift(id);
		Add(id << 1, l, r, x, L, mid);
		Add(id<<1|1, l, r, x, mid, R);
		ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	void Add_Stop(int pos, int id){
		Stop.pb({pos, id});
	}
	void Add_Move(int pos, int id){
		Move.pb({pos, id});
	}
	void Init(){
		sz = Stop.size();
		if(Stop.empty())
			return ;

		for(auto &el : Stop)
			el.F /= spd;
		for(auto &el : Move)
			el.F /= spd;
		sort(all(Stop));

		ans.resize(sz * 4);
		mn.resize(sz * 4);
		lz.resize(sz * 4);
		Build(1, 0, sz);
	}
	void Infect_Move(int pos, int id, int tm){
		// debug(id);
		// debug(tm);
		pos /= spd;
		// int dbg = 0;
		// if(dbg){
		// for(auto el : Stop){
		// 	int i = el.S;
		// 	// cerr << "&& " << id << ' ' << i << '\n';
		// 	if(el.F < pos + tm) continue;
		// 	if(mk[i]) continue;
		// 	int ds = Collision(id, i);
		// 	assert(ds == el.F - pos);
		// 	if(dis[i] > ds){
		// 		st.erase({dis[i], i});
		// 		dis[i] = ds;
		// 		st.insert({ds, i});
		// 	}
		// }
		// }
		// for(auto [_pos, _id] : Stop){
		// 	if(mk[_id]) continue;
		// 	if(pos + tm <= _pos && !mk[_id]){
		// 		assert(Collision(id, _id) == _pos - pos);
		// 		if(dis[_id] > _pos - pos){
		// 			st.erase({dis[_id], _id});
		// 			dis[_id] = _pos - pos;
		// 			st.insert({dis[_id], _id});
		// 		}
		// 	}
		// }

		int idx = lower_bound(all(Stop), pii(pos + tm, -1)) - Stop.begin();
		if(idx == sz)
			return ;
		// debug(pos);
		Add(1, idx, sz, -pos, 0, sz);
		if(dis[ans[1].S] > ans[1].F){
			st.erase({dis[ans[1].S], ans[1].S});
			dis[ans[1].S] = ans[1].F;
			st.insert(ans[1]);
		}
	}
	void Infect_Stop(int pos, int id, int tm){
		pos /= spd;
		int idx = lower_bound(all(Stop), pii(pos, id)) - Stop.begin();
		// assert(idx < sz);
		assert(Stop[idx] == pii(pos, id));
		Off(1, idx, 0, sz);
		if(dis[ans[1].S] > ans[1].F){
			dis[ans[1].S] = ans[1].F;
			st.insert(ans[1]);
		}
	}
	void Reset(){
		Stop.clear();
		Move.clear();
	}
};

Line DIA[4][4][N], U[N], R[N]; 
int CP[N], CN[N], CXX[N], CYY[N];

int rv[4][4], ty[4][4];
void Infect(int u, int tm){
	// assert(mk[u] == 0);
	mk[u] = 1;
	// for(int i = 0; i < n; i++){
	// 	if(mk[i]) continue;
	// 	int ds = Collision(u, i);
	// 	if(ds != Inf)
	// 		vis.insert({u, i});

	// 	if(ds >= tm && ds != Inf && dis[i] > ds){
	// 		st.erase({dis[i], i});
	// 		dis[i] = ds;
	// 		st.insert({ds, i});
	// 	}
	// }
	// return ;
	// debug(u);
	int MAX = 1'000'000'000;
	int pos;
	for(int d2 = 0; d2 < 4; d2 ++){
		if((dir[u] + d2) % 2 == 0) continue;
		pos = rv[dir[u]][d2] ? MAX - x[u] : x[u];
		DIA[dir[u]][d2][ ty[dir[u]][d2] ? CN[u] : CP[u]].Infect_Move(pos, u, tm);
		
		pos = rv[d2][dir[u]] ? MAX - x[u] : x[u];
		DIA[d2][dir[u]][ ty[d2][dir[u]] ? CN[u] : CP[u]].Infect_Stop(pos, u, tm);
	}


	int imp = dir[u] & 1 ? y[u] : x[u];

	pos = rv[dir[u]][dir[u] ^ 2] ? MAX - imp : imp;
	DIA[dir[u]][dir[u] ^ 2][dir[u] & 1 ? CXX[u] : CYY[u]].Infect_Move(pos, u, tm);
	
	pos = rv[dir[u] ^ 2][dir[u]] ? MAX - imp : imp;
	DIA[dir[u] ^ 2][dir[u]][dir[u] & 1 ? CXX[u] : CYY[u]].Infect_Stop(pos, u, tm);

}




int Solve(){
	dir[0] = 0;
	for(int i = 1; i < n; i++){
		int X = abs(x[i] - x[0]);
		int Y = abs(y[i] - y[0]);
		if(X == Y){
			if(x[i] < x[0]) dir[i] = 0;
			else dir[i] = y[i] < y[0] ? 3 : 1;
		} else {
			if(X > Y){
				if( x[i] < x[0]) dir[i] = 0;
				else dir[i] = 2;
			} else {
				if( y[i] < y[0]) dir[i] = 3;
				else dir[i] = 1;
			}
		}
	}
	// cerr << "!! " ;
	// for(int i = 0; i < n; i++){
	// 	cerr << dir[i] << ' ';
	// }
	// cerr << '\n';

	// cerr << "!! " << x[0] << ' ' << y[0] << ' ' << x[1] << ' ' << y[1] << '\n';
	// for(int i = 0; i < N; i++) R[i].Reset(), U[i].Reset();
	for(int i = 0; i < 16; i++)
		for(int j = 0; j < N; j++)
			DIA[i >> 2][i & 3][j].Reset();

	for(int i = 0; i < 4; i++) 
		for(int j = 0; j < N; j++)
			DIA[i][i ^ 2][j].spd = 2;

	int MAX = 1'000'000'000;
	for(int i = 0; i < n; i++){
		int pos;
		for(int d2 = 0; d2 < 4; d2 ++){
			if((dir[i] + d2) % 2 == 0) continue;
			
			pos = rv[dir[i]][d2] ? MAX - x[i] : x[i];
			DIA[dir[i]][d2][ ty[dir[i]][d2] ? CN[i] : CP[i]].Add_Move(pos, i);
			
			pos = rv[d2][dir[i]] ? MAX - x[i] : x[i];
			DIA[d2][dir[i]][ ty[d2][dir[i]] ? CN[i] : CP[i]].Add_Stop(pos, i);
		}

		int imp = dir[i] & 1 ? y[i] : x[i];

		pos = rv[dir[i]][dir[i] ^ 2] ? MAX - imp : imp;
		DIA[dir[i]][dir[i] ^ 2][dir[i] & 1 ? CXX[i] : CYY[i]].Add_Move(pos, i);
		
		pos = rv[dir[i] ^ 2][dir[i]] ? MAX - imp : imp;
		DIA[dir[i] ^ 2][dir[i]][dir[i] & 1 ? CXX[i] : CYY[i]].Add_Stop(pos, i);	
	}
	for(int i = 0; i < 16; i++)
		for(int j = 0; j < N; j++)
			DIA[i >> 2][i & 3][j].Init();

	memset(mk, 0, sizeof mk);
	fill(dis, dis + N, Inf);

	dis[0] = 0;
	st.insert({0, 0});
	while(!st.empty()){
		// cerr << "&&&&&&&\n";
		// for(auto [a1, a2] : st)
		// 	cerr << a1 << ' ' << a2 << '\n';
		// cerr << "-------\n";
		int fr = st.begin() -> S;
		int tm = st.begin() -> F;
		st.erase(st.begin());
		// if(tm > Inf) continue;
		// cerr << "!! " << fr << ' ' << tm << '\n';
		Infect(fr, tm);
	}


	int res = 0;
	for(int i = 0; i < n; i++)
		res += mk[i];
	return res;
}


int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	rv[3][0] = 1; rv[1][0] = 1;
	rv[2][1] = 1; rv[2][3] = 1;
	rv[2][0] = 1; rv[1][3] = 1;

	ty[0][1] = ty[1][0] = ty[2][3] = ty[3][2] = 1;

	cin >> n;
	vector<int> cp, cn, cxx, cyy;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i];
		cp.pb(x[i] + y[i]);
		cn.pb(x[i] - y[i]);
		cxx.pb(x[i]);
		cyy.pb(y[i]);
	}
	sort(all(cp));
	sort(all(cn));
	sort(all(cxx));
	sort(all(cyy));
	for(int i = 0; i < n; i++)
		CP[i] = lower_bound(all(cp), x[i] + y[i]) - cp.begin();
	for(int i = 0; i < n; i++)
		CN[i] = lower_bound(all(cn), x[i] - y[i]) - cn.begin();
	for(int i = 0; i < n; i++)
		CXX[i] = lower_bound(all(cxx), x[i]) - cxx.begin();
	for(int i = 0; i < n; i++)
		CYY[i] = lower_bound(all(cyy), y[i]) - cyy.begin();

	for(int i = 0; i < n; i++){
		x[i] += x[i];
		y[i] += y[i];
	}
	
	int ans = 0;
	int MAX = 1'000'000'000;
	for(int _ = 0; _ < 4; _++){

		ans = max(ans, Solve());
		for(int i = 0; i < n; i++){
			int _x = x[i];
			x[i] = MAX-y[i];
			y[i] = _x;
		}
		for(int i = 0; i < n; i++)
			swap(CP[i], CN[i]);

		for(int i = 0; i < n; i++)
			swap(CXX[i], CYY[i]);
		// break;
	}
	cout << ans << '\n';
	// for(auto [a1, a2] : vis)
	// 	cerr << "! " << a1 << ' ' << a2 << '\n';
	return 0;
}

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