제출 #585507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585507		abcvuitunggio	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	598 ms	35520 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define int long long
using namespace std;
const int mx=200000;
struct T{
    int cnt,sum;
}st[4*mx][2];
int k,n,s,t,res,id,val[mx+1],mn;
char p,q;
vector <pair <int, int> > v;
vector <int> v2;
map <int, int> mp;
bool cmp(pair <int, int> a, pair <int, int> b){
    return a.first+a.second<b.first+b.second;
}
void update(int node, int l, int r, int x, int v, int idx){
    if (l>x||r<x||l>r)
        return;
    if (l==r){
        st[node][idx].cnt+=v;
        st[node][idx].sum+=v*val[l];
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,x,v,idx);
    update(node<<1|1,mid+1,r,x,v,idx);
    st[node][idx].sum=st[node<<1][idx].sum+st[node<<1|1][idx].sum;
    st[node][idx].cnt=st[node<<1][idx].cnt+st[node<<1|1][idx].cnt;
}
int get(int node, int l, int r, int x, int idx){
    if (l==r)
        return (st[node][idx].cnt-x*2+2)*val[l];
    int mid=(l+r)>>1;
    if (st[node<<1][idx].cnt>=x)
        return st[node<<1|1][idx].sum+get(node<<1,l,mid,x,idx);
    return get(node<<1|1,mid+1,r,x-st[node<<1][idx].cnt,idx)-st[node<<1][idx].sum;
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> k >> n;
    for (int i=0;i<n;i++){
        cin >> p >> s >> q >> t;
        if (p==q){
            res+=abs(s-t);
            continue;
        }
        v.push_back(make_pair(min(s,t),max(s,t)));
    }
    res+=v.size();
    for (auto i:v){
        v2.push_back(i.first);
        v2.push_back(i.second);
    }
    sort(v2.begin(),v2.end());
    if (k==1){
        for (int i:v2)
            res+=abs(i-v2[v2.size()/2]);
        cout << res;
        return 0;
    }
    for (int i:v2)
        if (!mp.count(i)){
            mp[i]=++id;
            val[id]=i;
        }
    sort(v.begin(),v.end(),cmp);
    for (auto i:v){
        update(1,1,mx,mp[i.first],1,1);
        update(1,1,mx,mp[i.second],1,1);
    }
    mn=get(1,1,mx,st[1][1].cnt/2+1,1);
    for (auto i:v){
        update(1,1,mx,mp[i.first],1,0);
        update(1,1,mx,mp[i.second],1,0);
        update(1,1,mx,mp[i.first],-1,1);
        update(1,1,mx,mp[i.second],-1,1);
        mn=min(mn,get(1,1,mx,st[1][0].cnt/2+1,0)+get(1,1,mx,st[1][1].cnt/2+1,1));
    }
    cout << res+mn;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37