Submission #1159181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159181		AlgorithmWarrior	Palembang Bridges (APIO15_bridge)	C++20	22 / 100	68 ms	5960 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=2e5+5;
struct location{
    int pos;
    char type;
    int id;
    bool operator<(location ot){
        return pos<ot.pos;
    }
}loc[MAX];
int k,n;
long long s_init;
int total_loc;

void read(){
    cin>>k>>n;
    int i;
    for(i=1;i<=n;++i){
        char t1,t2;
        int p1,p2;
        cin>>t1>>p1>>t2>>p2;
        s_init+=abs(p2-p1);
        if(t1!=t2){
            loc[++total_loc]={p1,t1,i};
            loc[++total_loc]={p2,t2,i};
            ++s_init;
        }
    }
    sort(loc+1,loc+total_loc+1);
}

bool gasit_per[MAX];

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

long long spate[MAX],fata[MAX];

void precalc(int inc,int fin,long long v[],int incr){
    long long nr=0;
    int nrper=0;
    int i;
    for(i=1;i<=n;++i)
        gasit_per[i]=0;
    for(i=inc;i!=fin+incr;i+=incr){
        if(i!=inc)
            nr+=2LL*nrper*abs(loc[i-incr].pos-loc[i].pos);
        v[i]=nr;
        if(!gasit_per[loc[i].id])
            gasit_per[loc[i].id]=1;
        else
            ++nrper;
    }
}

long long solve(){
    precalc(1,total_loc,spate,1);
    precalc(total_loc,1,fata,-1);
    long long rasp=INF;
    int i;
    for(i=1;i<=total_loc;++i)
        minself(rasp,spate[i]+fata[i]);
    return rasp;
}

int main()
{
    read();
    if(total_loc)
        cout<<solve()+s_init;
    else
        cout<<s_init;
    return 0;
}

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