제출 #1159569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159569		AlgorithmWarrior	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	269 ms	12124 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};
        }
    }
    sort(intv+1,intv+total+1);
}

long long 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;
    long long sum=0;
    for(i=0;i<(int)poz.size();++i)
        sum+=abs(poz[median]-poz[i]);
    return sum;
}

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;
    big.insert(val2);
    sb+=val2;
    if(*small.rbegin()>*big.begin()){
        int nr1=*small.rbegin();
        int nr2=*big.begin();
        small.erase(small.find(nr1));
        ss-=nr1;
        small.insert(nr2);
        ss+=nr2;
        big.erase(big.find(nr2));
        sb-=nr2;
        big.insert(nr1);
        sb+=nr1;
    }
}

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;
    }
}

long long 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);
    }
    return minim;
}

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

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