제출 #284712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284712		doowey	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	951 ms	40316 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


// why would anyone write this
const int N = (int)1e5 + 10;
const int M = N * 2;

vector<int> uni;
int id(int x){
    return lower_bound(uni.begin(), uni.end(), x) - uni.begin();
}

ll pf[N];
ll suf[N];

struct Node{
    ll sum;
    ll cnt;
};

struct SegTree{
    Node T[M * 4 + 512];
    void init(){
        for(int i = 0 ;i < M * 4 + 512; i ++ )
            T[i] = {0, 0};
    }
    void upd(int node, int cl, int cr, int pos, int v){
        if(cl == cr){
            T[node].sum += v;
            T[node].cnt ++ ;
            return;
        }
        int mid = (cl + cr) / 2;
        if(mid >= pos)
            upd(node * 2, cl, mid, pos, v);
        else
            upd(node * 2 + 1, mid + 1, cr, pos, v);
        T[node].sum = T[node * 2].sum + T[node * 2 + 1].sum;
        T[node].cnt = T[node * 2].cnt + T[node * 2 + 1].cnt;
    }

    Node get(int node, int cl, int cr, int tl, int tr){
        if(cr < tl || cl > tr)
            return {0,0};
        if(cl >= tl && cr <= tr){
            return T[node];
        }
        int mid = (cl + cr) / 2;
        Node lef = get(node * 2, cl, mid, tl, tr);
        Node rig = get(node * 2 + 1, mid + 1, cr, tl, tr);
        lef.sum += rig.sum;
        lef.cnt += rig.cnt;
        return lef;
    }
};

SegTree up, down;
multiset<int> low, high;

bool comp(pii a, pii b){
    return a.fi + a.se < b.fi + b.se;
}

int main(){
    fastIO;
    int k, n;
    cin >> k >> n;
    vector<pii> posi;
    char a1, a2;
    int f1, f2;
    ll total = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> a1 >> f1 >> a2 >> f2;
        if(a1 == a2){
            total += abs(f2-f1);
        }
        else{
            total ++ ;
            if(a1 == 'B'){
                swap(f1, f2);
            }
            posi.push_back(mp(f1, f2));
            uni.push_back(f1);
            uni.push_back(f2);
        }
    }
    sort(uni.begin(), uni.end());
    uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
    sort(posi.begin(), posi.end(), comp);
    int sz = uni.size();
    int fe, fp;
    int med;
    ll dist;
    for(int i = 0 ; i < posi.size(); i ++ ){
        low.insert(posi[i].fi);
        high.insert(posi[i].se);
        while(1){
            auto en = low.end();
            en -- ;
            auto pv = high.begin();
            fe = *en;
            fp = *pv;
            if(fe > fp){
                low.erase(en);
                high.erase(pv);
                low.insert(fp);
                high.insert(fe);
            }
            else{
                break;
            }
        }
        up.upd(1, 0, sz - 1, id(posi[i].fi), posi[i].fi);
        down.upd(1, 0, sz - 1, id(posi[i].se), posi[i].se);
        auto it = low.end();
        -- it;
        med = *it;
        dist = 0;
        Node lf = up.get(1, 0, sz - 1, 0, id(med)-1);
        Node rf = up.get(1, 0, sz - 1, id(med)+1, sz - 1);
        dist += med * 1ll * lf.cnt - lf.sum;
        dist += rf.sum - med * 1ll * rf.cnt;
        lf = down.get(1, 0, sz - 1, 0, id(med)-1);
        rf = down.get(1, 0, sz - 1, id(med)+1, sz - 1);
        dist += med * 1ll * lf.cnt - lf.sum;
        dist += rf.sum - med * 1ll * rf.cnt;
        pf[i + 1] = dist;
    }
    up.init();
    down.init();
    low.clear();
    high.clear();
    for(int i = posi.size() - 1;i >= 0 ; i -- ){
        low.insert(posi[i].fi);
        high.insert(posi[i].se);
        while(1){
            auto en = low.end();
            en -- ;
            auto pv = high.begin();
            fe = *en;
            fp = *pv;
            if(fe > fp){
                low.erase(en);
                high.erase(pv);
                low.insert(fp);
                high.insert(fe);
            }
            else{
                break;
            }
        }
        up.upd(1, 0, sz - 1, id(posi[i].fi), posi[i].fi);
        down.upd(1, 0, sz - 1, id(posi[i].se), posi[i].se);
        auto it = low.end();
        -- it;
        med = *it;
        dist = 0;
        Node lf = up.get(1, 0, sz - 1, 0, id(med)-1);
        Node rf = up.get(1, 0, sz - 1, id(med)+1, sz - 1);
        dist += med * 1ll * lf.cnt - lf.sum;
        dist += rf.sum - med * 1ll * rf.cnt;
        lf = down.get(1, 0, sz - 1, 0, id(med)-1);
        rf = down.get(1, 0, sz - 1, id(med)+1, sz - 1);
        dist += med * 1ll * lf.cnt - lf.sum;
        dist += rf.sum - med * 1ll * rf.cnt;
        suf[i + 1] = dist;
    }
    if(k == 1){
        cout << total+pf[(int)posi.size()] << "\n";
    }
    else{
        ll ans = (ll)1e14;
        for(int i = 0 ; i <= posi.size(); i ++ )
            ans = min(ans, pf[i] + suf[i + 1]);
        cout << total+ans << "\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i = 0 ; i < posi.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~~
bridge.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for(int i = 0 ; i <= posi.size(); i ++ )
      |                         ~~^~~~~~~~~~~~~~

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