제출 #422292

#제출 시각아이디문제언어결과실행 시간메모리
422292Pbezz전선 연결 (IOI17_wiring)C++14
0 / 100
37 ms4908 KiB
#include "wiring.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back typedef pair<ll,ll> pii; typedef tree<ll, null_type,less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; const ll MAXN = 2e5+4; const ll INF = 1e9+7; ll get(ll a, ll b){ ll l=0,r=b-1,ans=0; while(l<a&&r>=0){ ans+=r+a-l; l++; r--; } if(l>=a){ while(r>=0){ ans+=r+1; r--; } }else{ while(l<a){ ans+=a-l; l++; } } return ans; } long long min_total_length(std::vector<int> r, std::vector<int> b){ ll n=(ll)r.size(), m=(ll)b.size(),ans=0; ll k,i,a; pair<ll,ll> pos[n+m]; for(i=0;i<n;i++)pos[i]={r[i],1}; for(i=0;i<m;i++)pos[i+n]={b[i],0}; sort(pos,pos+n+m); vector<pair<ll,ll>>meh; for(i=0;i<n+m;i++){ k=1; while(i<n+m-1 && pos[i+1].second==pos[i].second ){ i++; k++; } meh.pb({k,pos[i].second}); } n = (ll)meh.size(); if(n==2)return get(meh[0].first,meh[1].first); for(i=0;i<n-1;i++){ if(i==0){ k = meh[1].first; if(meh[0].first>meh[2].first){ k++; if(meh[1].first%2==1)meh[1].first--; } k/=2; ans+=get(meh[0].first,k); }else if(i==n-2){ k = meh[n-2].first; if(meh[n-3].first<meh[n-1].first){ k++; if(meh[n-2].first%2==1)meh[n-2].first--; } k/=2; ans+=get(k,meh[n-1].first); }else{ k = meh[i].first; if(meh[i-1].first<meh[i+1].first){ k++; if(meh[i].first%2==1)meh[i].first--; } k/=2; a = meh[i+1].first; if(meh[i].first>meh[i+2].first){ a++; if(meh[i+1].first%2==1)meh[i+1].first--; } a/=2; ans+=get(k,a); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...