Submission #1321122

#TimeUsernameProblemLanguageResultExecution timeMemory
1321122vtnooCoin Collecting (JOI19_ho_t4)C++20
100 / 100
69 ms12008 KiB
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<ll, ll>
using namespace std;
const int N=2e5+5;
const ll inf=1e18;
ll cnt1[N],cnt2[N];
void chmin(ll &a,ll b){
	a=min(a,b);
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	int n;cin>>n;
	vector<ii>v;
	L(i,0,n*2-1){
		int a,b;cin>>a>>b;
		v.pb(a,b);
	}
	vector<ii>v1,v2;
	L(i,0,n*2-1){
		if(llabs(v[i].snd-1)<=llabs(v[i].snd-2)){
			v1.pb(v[i]);
		}else v2.pb(v[i]);
	}
	sort(all(v1));
	sort(all(v2));
	ll def1=0,def2=0;
	ll ans=0;
	L(i,0,sz(v1)-1){
		ll x=v1[i].fst;
		if(x<1){
			cnt1[1]++;
			ans+=llabs(v1[i].fst-1)+llabs(v1[i].snd-1);
		}
		else if(x>n){
			cnt1[n]++;
			ans+=llabs(v1[i].fst-n)+llabs(v1[i].snd-1);
		}
		else{
			cnt1[v1[i].fst]++;
			ans+=llabs(v1[i].snd-1);
		}
	}
	L(i,0,sz(v2)-1){
		ll x=v2[i].fst;
		if(x<1){
			cnt2[1]++;
			ans+=llabs(v2[i].fst-1)+llabs(v2[i].snd-2);
		}
		else if(x>n){
			cnt2[n]++;
			ans+=llabs(v2[i].fst-n)+llabs(v2[i].snd-2);
		}
		else{
			cnt2[v2[i].fst]++;
			ans+=llabs(v2[i].snd-2);
		}
	}
	L(i,1,n){
		def1+=cnt1[i]-1;
		def2+=cnt2[i]-1;
		if(def1>0&&def2<0){
			ll vert=min(def1,-def2);
			def1-=vert;
			def2+=vert;
			ans+=vert;
		}else if(def1<0&&def2>0){
			ll vert=min(-def1,def2);
			def1+=vert;
			def2-=vert;
			ans+=vert;
		}
		ans+=abs(def1)+abs(def2);
	}
	cout<<ans<<endl;
}	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...