제출 #1318340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318340		JuanJL	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	1 ms	332 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i< b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

int main(){
	ll n; cin>>n;
	vector<pair<ll,ll>> p(2*n); forn(i,0,2*n) cin>>p[i].fst>>p[i].snd;
	sort(ALL(p));

	ll res=0;
	pair<ll,ll> newp;
	forn(i,0,2*n){
		newp.fst=min(n,max((ll)1,p[i].fst));
		newp.snd=min((ll)2,max((ll)1,p[i].snd));
		res+=abs(p[i].fst-newp.fst)+abs(p[i].snd-newp.snd);

		p[i]=newp;
	}

	vector<vector<ll>> matrix(2,vector<ll>(n,0));
	forn(i,0,2*n) matrix[p[i].snd-1][p[i].fst-1]++;
	
	ll cnt1 = 0;
	ll cnt2 = 0;

	forn(i,0,n){
		cnt1+=matrix[0][i];
		cnt2+=matrix[1][i];
	}

	if(cnt1<cnt2){
		swap(matrix[0],matrix[1]);
	}

	ll acnt1= 0;
	ll acnt2= 0;

	/*forn(j,0,2){
		forn(i,0,n) cout<<matrix[j][i]<<" "; cout<<'\n';
	}

	cout<<res<<'\n';*/
	
	forn(i,0,n){
		//cout<<i<<" ---- "<<i+1<<'\n';
		acnt1+=matrix[0][i];
		if(acnt1<i+1) res+=(i+1)-acnt1;
		ll ext1 = max((ll)0,acnt1-(i+1));

		acnt2+=matrix[1][i];
		ll ext2 = acnt2-(i+1);

		if(ext2<0 && ext1>0){
			ll aux = min(ext1, -ext2);
			acnt2+=aux;
			acnt1-=aux;
			ext2+=aux;
			ext1-=aux;
			res+=aux;
		}

		//cout<<ext1<<" "<<ext2<<'\n';
		res+=ext1;
		res+=abs(ext2);
		//cout<<res<<'\n';
	}

	cout<<res<<'\n';
	return 0;
}

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