Submission #1318347

#TimeUsernameProblemLanguageResultExecution timeMemory
1318347JuanJLCoin Collecting (JOI19_ho_t4)C++20
100 / 100
149 ms5832 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...