Submission #45294

#	Time	Username	Problem	Language	Result	Execution time	Memory
45294		JohnTitor	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	53 ms	4568 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Palembang_Bridges"
int k, n;
ll sure=0;
deque <pair <ll, ll> > cross;
namespace one{
    vector <ll> pos;
    void solve(){
        for(pair <ll, ll> p: cross){
            pos.pb(p.first);
            pos.pb(p.second);
        }
        sort(pos.begin(), pos.end());
        ll x=pos[pos.size()/2];
        ll res=0;
        for(ll p: pos) res+=abs(p-x);
        write(res+sure);
    }
}
namespace two{
    vector <ll> frwd;
    vector <ll> bkwd;
    class dynamic_nearest{
    public:
        multiset <ll> low, high;
        ll sumlow, sumhigh;
        void shift(){
            while(low.size()>high.size()){
                high.insert(*low.rbegin());
                sumhigh+=(*low.rbegin());
                sumlow-=(*low.rbegin());
                low.erase(low.find(*low.rbegin()));
            }
            while((!low.empty())&&((*low.rbegin())>(*high.begin()))){
                ll a=*low.rbegin();
                ll b=*high.begin();
                sumlow-=a;
                sumhigh-=b;
                low.erase(low.find(*low.rbegin()));
                high.erase(high.begin());
                low.insert(b);
                sumlow+=b;
                high.insert(a);
                sumhigh+=a;
            }
        }
        void insert(ll x){
            low.insert(x);
            sumlow+=x;
            shift();
        }
        void clear(){
            low.clear();
            high.clear();
            sumlow=sumhigh=0;
        }
        ll cost(){
            if(high.empty()) return 0;
            return (sumhigh-sumlow)-((*high.begin())*(high.size()-low.size()));
        }
    } DN;
    void solve(){
        sort(cross.begin(), cross.end(), [](pair <ll, ll> a, pair <ll, ll> b){
            return a.first+a.second<b.first+b.second;
        });
        DN.clear();
        for(pair <ll, ll> p: cross){
            DN.insert(p.first);
            DN.insert(p.second);
            frwd.pb(DN.cost());
        }
        reverse(cross.begin(), cross.end());
        DN.clear();
        for(pair <ll, ll> p: cross){
            DN.insert(p.first);
            DN.insert(p.second);
            bkwd.pb(DN.cost());
        }
        reverse(bkwd.begin(), bkwd.end());
        ll res=bkwd[0];
        bkwd.pb(0);
        FFOR(i, 0, n) res=min(res, frwd[i]+bkwd[i+1]);
        writeln(res+sure);
    }
}
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(k);
    read(n);
    sure=n;
    {
        char c0, c1;
        ll x0, x1;
        FOR(i, 1, n){
            while(!isalpha(c0=getchar()));
            read(x0);
            while(!isalpha(c1=getchar()));
            read(x1);
            if(c0==c1) sure+=abs(x0-x1)-1;
            else{
                if(x0>x1) swap(x0, x1);
                cross.pb(mp(x0, x1));
            }
        }
    }
    if(k==1) one::solve();
    else two::solve();
}

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