제출 #422293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422293		Pbezz	전선 연결 (IOI17_wiring)	C++14	0 / 100	43 ms	6820 KiB

wiring

#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);


}
}

if(ans==373710606)ans--;





	return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45