Submission #850654

#	Time	Username	Problem	Language	Result	Execution time	Memory
850654		willychan	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	1 ms	604 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
bool cnt[200005][2];


int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll ans = 0;
	int n;cin>>n;
	map<int,int> mp[2];
	for(int i=0;i<2*n;i++){
		int x,y;cin>>x>>y;	
		if(y>=2){
			if(x<1){
				mp[1][1]++;
				cnt[1][1]=1;
				ans+=abs(x-1)+abs(y-2);
			}else if(x>n){
				mp[n][1]++;
				cnt[n][1]=1;
				ans+=abs(x-n)+abs(y-2);
			}else{
				mp[1][x]++;
				cnt[x][1]=1;
				ans+=abs(y-2);
			}
		}else{
			if(x<1)	{
				mp[0][1]++;
				cnt[1][0]=1;
				ans+=abs(x-1)+abs(y-1);
			}else if(x>n){
				mp[0][n]++;
				cnt[n][0]=1;
				ans+=abs(x-n)+abs(y-1);
			}else{
				mp[0][x]++;
				cnt[x][0]=1;
				ans+=abs(y-1);
			}
		}
	}
	for(auto i : mp[0]){
		mp[0][i.first]--;
		if(mp[0][i.first]==0) mp[0].erase(i.first);
	}
	for(auto i : mp[1]){
		mp[1][i.first]--;
		if(mp[1][i.first]==0) mp[1].erase(i.first);
	}
	for(int j=0;j<=1;j++){
		for(int i=1;i<=n;i++){
			if(cnt[i][j]) continue;
			auto low = mp[j].lower_bound(i);	
			pair<int,int> result = {1e9,0};
			if(low==mp[j].end()){
				if(mp[j].size()) result = min(result,make_pair(abs(mp[j].rbegin()->first-i),mp[j].rbegin()->first));				
			}else if(low==mp[j].begin()){
				result = min(result,make_pair(abs(low->first-i),low->first));	
			}else{
				auto pv = prev(low);	
				result = min(result,make_pair(abs(low->first-i),low->first));
				result = min(result,make_pair(abs(pv->first-i),pv->first));
			}
			auto low2 = mp[j^1].lower_bound(i);
			pair<int,int> result2 = {1e9,0};
			if(low2==mp[j^1].end()){
				if(mp[j^1].size()) result2 = min(result2,make_pair(abs(mp[j^1].rbegin()->first-i)+1,mp[j^1].rbegin()->first));				
			}else if(low2==mp[j^1].begin()){
				result2 = min(result2,make_pair(abs(low2->first-i)+1,low2->first));	
			}else{
				auto pv = prev(low2);	
				result2 = min(result2,make_pair(abs(low2->first-i)+1,low2->first));
				result2 = min(result2,make_pair(abs(pv->first-i)+1,pv->first));
			}
			if(result.first<result2.first){
				ans+=result.first;
				mp[j][result.second]--;
//				cout<<j<<"\n";
				if(mp[j][result.second]==0) mp[j].erase(result.second);
			}else{
				ans+=result2.first;
				mp[j^1][result2.second]--;
//				cout<<(j^1)<<"\n";
				if(mp[j^1][result2.second]==0) mp[j^1].erase(result2.second);
			}
			//cout<<i<<" "<<j<<" "<<ans<<"\n";
		}
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63