제출 #1010326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010326		GrindMachine	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	125 ms	9552 KiB

bridge

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

points on the same side: cost = abs(x-y)
only consider points on opposite sides
wlog, x < y

for k = 1, find s s.t:
sum{ abs(x-s)+abs(y-s) } is minimized
consider each x and y point on a number line (total = 2n points)
best s = median of these 2n points (the nth point)

for k = 2, visualize each (x,y) point on the 2d plane (x = row, y = col)
pick 2 points (s,s) and (t,t) s.t:
sum{ min(abs(x-s)+abs(y-s),abs(x-t)+abs(y-t)) } is minimized
can be rewritten as:
sum{ min(dis(x,y,s,s),dis(x,y,t,t)) } (dis(x1,y1,x2,y2) = manhattan distance between points (x1,y1) and (x2,y2))

the line connecting (s,s) and (t,t) is a diagonal
rotate the plane by 45 deg => it is now a straight line
draw the perpendicular bisector of the line (at the midpoint)
points on one side go to s and points on the other side go to t

on the original graph, the perpendicular bisector is an antidiagonal passing through ((s+t)/2,(s+t)/2)

\  / => bisector
 \/
 /\
/  \ => line connecting (s,s) and (t,t)

all points on the left with x+y <= s+t go to s
all points on the right with x+y > s+t go to t
sort all points by x+y
some pref of points go to s, the rest of the points go to t
for each splitting, find the best min cost for all points to meet at a single point (like k = 1 case)
can be sped up using fenwick trees that can handle lower_bound queries (can also use ordered set for this, but anyways need a fenwick tree for finding the sum on a segment)

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int n;
    vector<T> tr;
    int LOG = 0;

    fenwick() {

    }

    fenwick(int n_) {
        n = n_;
        tr = vector<T>(n + 1);
        while((1<<LOG) <= n) LOG++;
    }

    void reset(){
        fill(all(tr),0);
    }

    int lsb(int x) {
        return x & -x;
    }

    void pupd(int i, T v) {
        for(; i <= n; i += lsb(i)){
            tr[i] += v;
        }
    }

    T sum(int i) {
        T res = 0;
        for(; i; i ^= lsb(i)){
            res += tr[i];
        }
        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }

    int lower_bound(T s){
        // first pos with sum >= s
        if(sum(n) < s) return n+1;
        int i = 0;
        rev(bit,LOG-1,0){
            int j = i+(1<<bit);
            if(j > n) conts;
            if(tr[j] < s){
                s -= tr[j];
                i = j;
            }
        }

        return i+1;
    }

    int upper_bound(T s){
        return lower_bound(s+1);
    }
};

void solve(int test_case)
{
    ll k,n; cin >> k >> n;
    vector<array<ll,3>> a;
    ll same_side = 0;
    map<ll,ll> mp;

    rep1(i,n){
        char p,q; ll x,y;
        cin >> p >> x >> q >> y;
        if(p == q){
            same_side += abs(x-y);
        }
        else{
            if(x > y) swap(x,y);
            a.pb({x+y,x,y});
        }
    }

    sort(all(a));

    auto go = [&](vector<array<ll,3>> &curr){
        vector<ll> b;
        for(auto [val,x,y] : curr){
            b.pb(x), b.pb(y);
        }

        sort(all(b));
        ll s = -1;
        if(!b.empty()){
            s = b[sz(b)/2];
        }

        ll res = 0;
        trav(x,b){
            res += abs(x-s);
        }

        return res;
    };

    if(k == 1 or a.empty()){
        ll ans = go(a);
        ans += same_side+sz(a);
        cout << ans << endl;
        return;
    }

    n = sz(a);
    a.insert(a.begin(),{-1,-1,-1});
    vector<ll> b;
    rep1(i,n) b.pb(a[i][1]), b.pb(a[i][2]);
    b.pb(-1);
    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    ll siz = sz(b);

    vector<ll> pref(n+5), suff(n+5);
    fenwick<ll> fenw_cnt(siz+5), fenw_sum(siz+5);

    auto ins = [&](ll x){
        ll i = lower_bound(all(b),x)-b.begin();
        fenw_cnt.pupd(i,1);
        fenw_sum.pupd(i,x);
    };

    auto get = [&](ll mid){
        ll i = fenw_cnt.lower_bound(mid);
        ll cnt1 = fenw_cnt.query(1,i-1), sum1 = fenw_sum.query(1,i-1);
        ll cnt2 = fenw_cnt.query(i+1,siz), sum2 = fenw_sum.query(i+1,siz);
        return b[i]*cnt1-sum1+sum2-b[i]*cnt2;
    };

    rep1(i,n){
        ins(a[i][1]), ins(a[i][2]);
        pref[i] = get(i);
    }

    fenw_cnt.reset(), fenw_sum.reset();

    rev(i,n,1){
        ins(a[i][1]), ins(a[i][2]);
        suff[i] = get(n-i+1);
    }

    ll ans = inf2;

    rep1(i,n){
        amin(ans,pref[i]+suff[i+1]);
    }

    ans += same_side+n;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

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