Submission #1164869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164869		emptypringlescan	IOI Fever (JOI21_fever)	C++20	100 / 100	1219 ms	74816 KiB

fever

#include <bits/stdc++.h>
using namespace std;
int n;
pair<long long,long long> arr[100005];
int dir[100005];
set<pair<long long,int> >::iterator it;
int solve(){
	unordered_map<long long,set<pair<long long,int> > > um[2][4],st[2][4];
	for(int i=0; i<n; i++){
		st[0][dir[i]][arr[i].first].insert({arr[i].second,i});
		st[1][dir[i]][arr[i].second].insert({arr[i].first,i});
		um[0][dir[i]][arr[i].first-arr[i].second].insert({arr[i].first,i});
		um[1][dir[i]][arr[i].first+arr[i].second].insert({arr[i].first,i});
	}
	int v[n][3],ded[n];
	memset(v,0,sizeof(v));
	memset(ded,0,sizeof(ded));
	priority_queue<pair<long long,pair<int,int> >,vector<pair<long long,pair<int,int> > >,greater<pair<long long,pair<int,int> > > > pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		long long tm=pq.top().first;
		int a=pq.top().second.first,b=pq.top().second.second;
		//cout << a << ' ' << b << '\n';
		pq.pop();
		if(!ded[a]){
			st[0][dir[a]][arr[a].first].erase({arr[a].second,a});
			st[1][dir[a]][arr[a].second].erase({arr[a].first,a});
			um[0][dir[a]][arr[a].first-arr[a].second].erase({arr[a].first,a});
			um[1][dir[a]][arr[a].first+arr[a].second].erase({arr[a].first,a});
			if(dir[a]==0){
				it=st[0][2][arr[a].first].lower_bound({arr[a].second+2*tm,-1});
				if(it!=st[0][2][arr[a].first].end()){
					pq.push({(abs(it->first-arr[a].second)+1)/2ll,{it->second,a}});
				}
				it=um[0][3][arr[a].first-arr[a].second].lower_bound({arr[a].first+tm,-1});
				if(it!=um[0][3][arr[a].first-arr[a].second].end()){
					pq.push({it->first-arr[a].first,{it->second,a}});
				}
				it=um[1][1][arr[a].first+arr[a].second].upper_bound({arr[a].first-tm,1e9});
				if(it!=um[1][1][arr[a].first+arr[a].second].begin()){
					it--;
					pq.push({arr[a].first-it->first,{it->second,a}});
				}
			}
			else if(dir[a]==1){
				it=st[1][3][arr[a].second].lower_bound({arr[a].first+2*tm,-1});
				if(it!=st[1][3][arr[a].second].end()){
					pq.push({(abs(it->first-arr[a].first)+1)/2ll,{it->second,a}});
				}
				it=um[0][2][arr[a].first-arr[a].second].lower_bound({arr[a].first+tm,-1});
				if(it!=um[0][2][arr[a].first-arr[a].second].end()){
					pq.push({it->first-arr[a].first,{it->second,a}});
				}
				it=um[1][0][arr[a].first+arr[a].second].lower_bound({arr[a].first+tm,-1});
				if(it!=um[1][0][arr[a].first+arr[a].second].end()){
					pq.push({it->first-arr[a].first,{it->second,a}});
				}
			}
			else if(dir[a]==2){
				it=st[0][0][arr[a].first].upper_bound({arr[a].second-2*tm,1e9});
				if(it!=st[0][0][arr[a].first].begin()){
					it--;
					pq.push({(abs(arr[a].second-it->first)+1)/2ll,{it->second,a}});
				}
				it=um[0][1][arr[a].first-arr[a].second].upper_bound({arr[a].first-tm,1e9});
				if(it!=um[0][1][arr[a].first-arr[a].second].begin()){
					it--;
					pq.push({arr[a].first-it->first,{it->second,a}});
				}
				it=um[1][3][arr[a].first+arr[a].second].lower_bound({arr[a].first+tm,-1});
				if(it!=um[1][3][arr[a].first+arr[a].second].end()){
					pq.push({it->first-arr[a].first,{it->second,a}});
				}
			}
			else{
				it=st[1][1][arr[a].second].upper_bound({arr[a].first-2*tm,1e9});
				if(it!=st[1][1][arr[a].second].begin()){
					it--;
					pq.push({(abs(arr[a].first-it->first)+1)/2ll,{it->second,a}});
				}
				it=um[0][0][arr[a].first-arr[a].second].upper_bound({arr[a].first-tm,1e9});
				if(it!=um[0][0][arr[a].first-arr[a].second].begin()){
					it--;
					pq.push({arr[a].first-it->first,{it->second,a}});
				}
				it=um[1][2][arr[a].first+arr[a].second].upper_bound({arr[a].first-tm,1e9});
				if(it!=um[1][2][arr[a].first+arr[a].second].begin()){
					it--;
					pq.push({arr[a].first-it->first,{it->second,a}});
				}
			}
			
		}
		ded[a]=1;
		if(arr[a].first==arr[b].first||arr[a].second==arr[b].second){
			if(v[a][0]) continue;
			v[a][0]=1;
			if(dir[b]==0){
				it=st[0][2][arr[b].first].lower_bound({arr[b].second+2*tm,-1});
				if(it!=st[0][2][arr[b].first].end()){
					pq.push({(it->first-arr[b].second+1)/2,{it->second,b}});
				}
			}
			else if(dir[b]==1){
				it=st[1][3][arr[b].second].lower_bound({arr[b].first+2*tm,-1});
				if(it!=st[1][3][arr[b].second].end()){
					pq.push({(it->first-arr[b].first+1)/2,{it->second,b}});
				}
			}
			else if(dir[b]==2){
				it=st[0][0][arr[b].first].upper_bound({arr[b].second-2*tm,1e9});
				if(it!=st[0][0][arr[b].first].begin()){
					it--;
					pq.push({(arr[b].second-it->first+1)/2,{it->second,b}});
				}
			}
			else{
				it=st[1][1][arr[b].second].upper_bound({arr[b].first-2*tm,1e9});
				if(it!=st[1][1][arr[b].second].begin()){
					it--;
					pq.push({(arr[b].first-it->first+1)/2,{it->second,b}});
				}
			}
		}
		else if(arr[a].first-arr[a].second==arr[b].first-arr[b].second){
			if(v[a][1]) continue;
			v[a][1]=1;
			if(dir[b]==0){
				it=um[0][3][arr[b].first-arr[b].second].lower_bound({arr[b].first+tm,-1});
				if(it!=um[0][3][arr[b].first-arr[b].second].end()){
					pq.push({it->first-arr[b].first,{it->second,b}});
				}
			}
			else if(dir[b]==1){
				it=um[0][2][arr[b].first-arr[b].second].lower_bound({arr[b].first+tm,-1});
				if(it!=um[0][2][arr[b].first-arr[b].second].end()){
					pq.push({it->first-arr[b].first,{it->second,b}});
				}
			}
			else if(dir[b]==2){
				it=um[0][1][arr[b].first-arr[b].second].upper_bound({arr[b].first-tm,1e9});
				if(it!=um[0][1][arr[b].first-arr[b].second].begin()){
					it--;
					pq.push({arr[b].first-it->first,{it->second,b}});
				}
			}
			else{
				it=um[0][0][arr[b].first-arr[b].second].upper_bound({arr[b].first-tm,1e9});
				if(it!=um[0][0][arr[b].first-arr[b].second].begin()){
					it--;
					pq.push({arr[b].first-it->first,{it->second,b}});
				}
			}
		}
		else{
			assert(arr[a].first+arr[a].second==arr[b].first+arr[b].second);
			if(v[a][2]) continue;
			v[a][2]=1;
			if(dir[b]==0){
				it=um[1][1][arr[b].first+arr[b].second].upper_bound({arr[b].first-tm,1e9});
				if(it!=um[1][1][arr[b].first+arr[b].second].begin()){
					it--;
					pq.push({arr[b].first-it->first,{it->second,b}});
				}
			}
			else if(dir[b]==1){
				it=um[1][0][arr[b].first+arr[b].second].lower_bound({arr[b].first+tm,-1});
				if(it!=um[1][0][arr[b].first+arr[b].second].end()){
					pq.push({it->first-arr[b].first,{it->second,b}});
				}
			}
			else if(dir[b]==2){
				it=um[1][3][arr[b].first+arr[b].second].lower_bound({arr[b].first+tm,-1});
				if(it!=um[1][3][arr[b].first+arr[b].second].end()){
					pq.push({it->first-arr[b].first,{it->second,b}});
				}
			}
			else{
				it=um[1][2][arr[b].first+arr[b].second].upper_bound({arr[b].first-tm,1e9});
				if(it!=um[1][2][arr[b].first+arr[b].second].begin()){
					it--;
					pq.push({arr[b].first-it->first,{it->second,b}});
				}
			}
		}
	}
	int ret=0;
	for(int i=0; i<n; i++) if(ded[i]) ret++;
	return ret;
}
int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> arr[i].first >> arr[i].second;
	}
	long long sm=arr[0].first+arr[0].second,df=arr[0].first-arr[0].second;
	dir[0]=0;
	for(int i=1; i<n; i++){
		if(arr[i].first-arr[i].second<df&&arr[i].first+arr[i].second>sm){
			dir[i]=2;
		}
		else if(arr[i].first-arr[i].second>=df&&arr[i].first+arr[i].second>sm){
			dir[i]=3;
		}
		else if(arr[i].first-arr[i].second>=df&&arr[i].first+arr[i].second<=sm){
			dir[i]=0;
		}
		else dir[i]=1;
	}
	int ans=0;
	ans=max(ans,solve());
	
	dir[0]=1;
	for(int i=1; i<n; i++){
		if(arr[i].first-arr[i].second<=df&&arr[i].first+arr[i].second>sm){
			dir[i]=2;
		}
		else if(arr[i].first-arr[i].second>df&&arr[i].first+arr[i].second>sm){
			dir[i]=3;
		}
		else if(arr[i].first-arr[i].second>df&&arr[i].first+arr[i].second<=sm){
			dir[i]=0;
		}
		else dir[i]=1;
	}
	ans=max(ans,solve());
	
	dir[0]=2;
	for(int i=1; i<n; i++){
		if(arr[i].first-arr[i].second<=df&&arr[i].first+arr[i].second>=sm){
			dir[i]=2;
		}
		else if(arr[i].first-arr[i].second>df&&arr[i].first+arr[i].second>=sm){
			dir[i]=3;
		}
		else if(arr[i].first-arr[i].second>df&&arr[i].first+arr[i].second<sm){
			dir[i]=0;
		}
		else dir[i]=1;
	}
	ans=max(ans,solve());
	
	dir[0]=3;
	for(int i=1; i<n; i++){
		if(arr[i].first-arr[i].second<df&&arr[i].first+arr[i].second>=sm){
			dir[i]=2;
		}
		else if(arr[i].first-arr[i].second>=df&&arr[i].first+arr[i].second>=sm){
			dir[i]=3;
		}
		else if(arr[i].first-arr[i].second>=df&&arr[i].first+arr[i].second<sm){
			dir[i]=0;
		}
		else dir[i]=1;
	}
	ans=max(ans,solve());
	cout << ans;
}

• 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: 31 / 31