Submission #284707

#	Time	Username	Problem	Language	Result	Execution time	Memory
284707		doowey	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	67 ms	4372 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;

ll solve(vector<pii> posi){
    vector<int> cor;
    for(auto x : posi){
        cor.push_back(x.fi);
        cor.push_back(x.se);
    }
    sort(cor.begin(), cor.end());
    ll answ = 0;
    if(cor.size() > 0){
        int med = cor[(int)cor.size() / 2];
        for(auto x : posi){
            answ += abs(med - x.fi);
            answ += abs(x.se - med);
        }
    }
    return answ;
}

multiset<int> low, high;
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(posi.begin(), posi.end());
    sort(uni.begin(), uni.end());
    uni.resize(unique(uni.begin(), uni.end()) - uni.begin());
    if(k == 1){
        cout << solve(posi) + total;
        return 0;
    }
    n = posi.size();
    ll res = (ll)1e14;
    for(int cut = 0; cut <= posi.size(); cut ++ ){
        vector<pii> lf, rf;
        for(int i = 0 ; i < cut ; i ++ ){
            lf.push_back(posi[i]);
        }
        for(int i = cut ; i < posi.size(); i ++ )
            rf.push_back(posi[i]);
        res = min(res, solve(lf) + solve(rf));
    }
    cout << res+total << "\n";
    return 0;
}

Compilation message (stderr)

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

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