제출 #1010316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010316		GrindMachine	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	126 ms	9632 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

/*



*/

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