제출 #1159550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159550		AlgorithmWarrior	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	70 ms	2752 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
int k,n;
long long rasp;
struct interval{
    int st,dr,mij;
    bool operator<(interval ot){
        return mij<ot.mij;
    }
}intv[MAX];
int total;
vector<int>poz;

void read(){
    cin>>k>>n;
    int i;
    for(i=1;i<=n;++i){
        char tip1,tip2;
        int poz1,poz2;
        cin>>tip1>>poz1>>tip2>>poz2;
        if(tip1==tip2)
            rasp+=abs(poz1-poz2);
        else{
            ++rasp;
            if(poz1>poz2)
                swap(poz1,poz2);
            intv[++total]={poz1,poz2,(poz1+poz2)/2};
        }
    }
    sort(intv+1,intv+total+1);
}

void solve1(){
    int i;
    for(i=1;i<=total;++i){
        poz.push_back(intv[i].st);
        poz.push_back(intv[i].dr);
    }
    sort(poz.begin(),poz.end());
    int median=poz.size()/2;
    for(i=0;i<(int)poz.size();++i)
        rasp+=abs(poz[median]-poz[i]);
}

multiset<int>small1,big1,small2,big2;
long long const INF=1e18;
long long ss1,sb1,ss2,sb2;

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

void add(multiset<int>&small,multiset<int>&big,long long& ss,long long& sb,int val1,int val2){
    small.insert(val1);
    ss+=val1;
    small.insert(val2);
    ss+=val2;
    int nr=*small.rbegin();
    small.erase(small.find(nr));
    ss-=nr;
    big.insert(nr);
    sb+=nr;
}

void del(multiset<int>&small,multiset<int>&big,long long& ss,long long& sb,int val1,int val2){
    if(small.find(val1)!=small.end()){
        small.erase(small.find(val1));
        ss-=val1;
    }
    else{
        big.erase(big.find(val1));
        sb-=val1;
    }
    if(small.find(val2)!=small.end()){
        small.erase(small.find(val2));
        ss-=val2;
    }
    else{
        big.erase(big.find(val2));
        sb-=val2;
    }
    if(small.size()<big.size()){
        int nr=*big.begin();
        big.erase(big.find(nr));
        sb-=nr;
        small.insert(nr);
        ss+=nr;
    }
    if(small.size()>big.size()){
        int nr=*small.rbegin();
        small.erase(small.find(nr));
        ss-=nr;
        big.insert(nr);
        sb+=nr;
    }
}

void solve2(){
    long long minim=INF;
    int i;
    for(i=1;i<=total;++i)
        add(small2,big2,ss2,sb2,intv[i].st,intv[i].dr);
    for(i=1;i<total;++i){
        del(small2,big2,ss2,sb2,intv[i].st,intv[i].dr);
        add(small1,big1,ss1,sb1,intv[i].st,intv[i].dr);
        minself(minim,sb1-ss1+sb2-ss2);
    }
    rasp+=minim;
}

int main(){
    read();
    if(k==1)
        solve1();
    else
        solve2();
    cout<<rasp;
    return 0;
}

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