제출 #1318347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318347		JuanJL	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	149 ms	5832 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];
	}

	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){
		acnt1+=matrix[0][i];
		acnt2+=matrix[1][i];

		ll ex1 = acnt1-(i+1);
		ll ex2 = acnt2-(i+1);

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

		res+=abs(ex1);
		res+=abs(ex2);
	}

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

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