| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 982901 | tamir1 | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
ll ans,n,k,i,j,x,y,l,m,a[200005],z,mn,a1,a2,m1,m2;
vector<pair<ll,ll>> v;
char s,t;
bool cmp(pair<ll,ll> a,pair<ll,ll> b){
return (double)(a.ff+a.ss)/2<(double)(b.ff+b.ss)/2;
}
ordered_set p,q;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> k >> n;
for(i=1;i<=n;i++){
cin >> s >> x >> t >> y;
if(s==t) ans+=abs(x-y);
else{
ans++;
l++;
a[l]=x;
l++;
a[l]=y;
if(x>y) swap(x,y);
v.push_back({x,y});
}
}
sort(a+1,a+l+1);
x=a[(l+1)/2];
if(k==1){
for(i=1;i<=l;i++){
ans+=abs(x-a[i]);
}
cout << ans;
return 0;}
sort(v.begin(),v.end(),cmp);
if(v.size()==0){
cout << ans;
return 0;
}
if(v.size()==1){
cout << ans+v[0].ss-v[0].ff;
return 0;
}
p.insert(v[0].ff);
p.insert(v[0].ss);
for(i=1;i<v.size();i++){
q.insert(v[i].ff);
q.insert(v[i].ss);
}
m1=*p.find_by_order(p.size()/2);
m2=*q.find_by_order(q.size()/2);
for(auto it=p.begin();it!=p.end();it++) a1+=abs(*it-m1);
for(auto it=q.begin();it!=q.end();it++) a2+=abs(*it-m2);
mn=a1+a2;
2 3 6 7
for(i=1;i<v.size()-1;i++){
ll x=v[i].ff,y=v[i].ss;
p.insert(x);
m=*p.find_by_order(p.size()/2);
a1+=abs(x-m1);
if(p.size()%2==1) a1-=abs(m1-m);
m1=m;
p.insert(y);
m=*p.find_by_order(p.size()/2);
a1+=abs(y-m1);
if(p.size()%2==1) a1-=abs(m1-m);
m1=m;
/*q.erase(q.upper_bound(x));
m=*q.find_by_order(q.size()/2);
if(q.size()%2==1) a2+=abs(m2-m);
a2-=(m2-x);
m2=m;
q.erase(q.upper_bound(y));
m=*q.find_by_order(q.size()/2);
if(q.size()%2==1) a2+=abs(m2-m);
a2-=(m2-y);
m2=m;
mn=min(mn,a1+a2);
p.insert(x);
p.insert(y);*/
q.erase(q.upper_bound(x));
q.erase(q.upper_bound(y));
//a1=0;
a2=0;
//m1=*p.find_by_order(p.size()/2);
m2=*q.find_by_order(q.size()/2);
//for(auto it=p.begin();it!=p.end();it++) a1+=abs(*it-m1);
for(auto it=q.begin();it!=q.end();it++) a2+=abs(*it-m2);
mn=min(mn,a1+a2);
}
cout << ans+mn;
}