Submission #1114361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114361		ShaShi	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2055 ms	105288 KiB

bridge

#include <bits/stdc++.h>
 
#define int long long 
 
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e18 + 7;
 
 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, res, pre_ans;
pii arr[MAXN], di[MAXN];
char ch, ch2;
vector<int> vec[2][MAXN], cmp;
int ps[2][MAXN], cnt[2][MAXN];



inline int id(int n) { return lower_bound(all(cmp), n)-cmp.begin(); }


vector<pii> _vec;
map<int, int> _cnt;

inline int solve1() {
    for (int i=1; i<=n; i++) {
        u = arr[i].F; v = arr[i].S;

        _cnt[u]++, _cnt[v]++, _vec.pb({u, v}), tmp2 += 2;
    }

    int res2 = 0;
 
    for (auto cur: _cnt) {
        tmp += cur.S;
 
        // cout << cur.F << " " << cur.S << endl;
 
        if (tmp+tmp >= tmp2) {
            tmp = cur.F;
            break;
        }
    }
 
    for (auto cur:_cnt) res2 += abs(cur.F-tmp)*cur.S;

    tmp = tmp2 = 0;
 
    return res2+_vec.size();
}


/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)


struct D {
    int sigmaL, sigmaR, cnt;

    D () {}
} seg[MAXN<<2], emp;


inline D merge(D x, D y) {
    D res;

    res.sigmaL = x.sigmaL+y.sigmaL;
    res.sigmaR = x.sigmaR+y.sigmaR;
    res.cnt = x.cnt+y.cnt;

    return res;
}


void add(int s, int ind, int l=0, int r=N, int id=1) {
    // if (id == 1) cout << "+ " << arr[ind].F << " " << arr[ind].S << " " << s << endl;

    if (l+1 == r) {
        seg[id].cnt++;
        seg[id].sigmaL += arr[ind].F;
        seg[id].sigmaR += arr[ind].S;

        return;
    }

    if (s < mid) add(s, ind, l, mid, lid);
    else add(s, ind, mid, r, rid);

    seg[id] = merge(seg[lid], seg[rid]);
}


void rem(int s, int ind, int l=0, int r=N, int id=1) {
    // if (id == 1) cout << "- " << arr[ind].F << " " << arr[ind].S << endl;

    if (l+1 == r) {
        seg[id].cnt--;
        seg[id].sigmaL -= arr[ind].F;
        seg[id].sigmaR -= arr[ind].S;

        return;
    }

    if (s < mid) rem(s, ind, l, mid, lid);
    else rem(s, ind, mid, r, rid);

    seg[id] = merge(seg[lid], seg[rid]);
}


D get(int s, int t, int l=0, int r=N, int id=1) {
    if (s >= t) return emp;
    if (s <= l && t >= r) return seg[id];
    if (t <= mid) return get(s, t, l, mid, lid);
    if (s >= mid) return get(s, t, mid, r, rid);
    return merge(get(s, t, l, mid, lid), get(s, t, mid, r, rid));
}

/* Segment Tree */


inline int cost(int x, int y) {
    int res = ps[0][x] + ps[1][y];

    D cur;
    cur = get(0, id(cmp[x]+cmp[y])); res += cur.sigmaL - cmp[x]*cur.cnt;
    cur = get(id(cmp[x]+cmp[y]), N); res += cmp[y]*cur.cnt - cur.sigmaR;

    return res;
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif
 
    cin >> k >> n;

    N = 0;
 
    for (int i=1; i<=n; i++) {
        cin >> ch >> u >> ch2 >> v;
 
        if (ch == ch2) res += abs(u-v);
        else arr[++N] = {u, v};
    }

    n = N; pre_ans = res; res += solve1();

    if (k == 1) kill(res);

    for (int i=1; i<=n; i++) {
        u = arr[i].F; v = arr[i].S;
        if (u > v) swap(arr[i].F, arr[i].S);
        pre_ans += abs(arr[i].F-arr[i].S)+1;
        cmp.pb(u); cmp.pb(v); cmp.pb(u+v);
    }

    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    N = cmp.size(); emp.sigmaL = emp.sigmaR = emp.cnt = 0;

    // cout << "@ " << endl;
    // for (int u:cmp) cout << u << " ";
    // cout << endl;


    for (int i=1; i<=n; i++) {
        u = di[i].F = id(arr[i].F);
        v = di[i].S = id(arr[i].S);

        cnt[0][u]++; cnt[1][v]++;
        vec[0][u].pb(i); vec[1][v].pb(i);
    }

    
    tmp = tmp2 = 0;
    
    for (int i=0; i<N; i++) {
        ps[0][i] = cmp[i]*tmp2-tmp;

        for (int ind:vec[1][i]) {
            tmp2++;
            tmp += arr[ind].S;
        }
    }


    tmp = tmp2 = 0;
    
    for (int i=N-1; i>=0; i--) {
        ps[1][i] = tmp-cmp[i]*tmp2;

        for (int ind:vec[0][i]) {
            tmp2++;
            tmp += arr[ind].F;
        }
    }

    // for (int i=1; i<=n; i++) add(id(arr[i].F+arr[i].S), i);

    ans = INF;
    int j = 1;

    for (int i=0; i<N; i++) {
        vector<int> temp;

        for (int j=i+1; j<N; j++) {
            // cout << "! " << i << " " << j << " : " << cmp[i] << " " << cmp[j] << " : " << cost(i, j) << " " << pre_ans+2*cost(i, j) << endl;


            ans = min(ans, pre_ans+2*cost(i, j));

            for (auto ind:vec[1][j]) {
                if (di[ind].F <= i) continue;

                temp.pb(ind); add(id(arr[ind].F+arr[ind].S), ind);
            }
        }

        for (auto ind:temp) rem(id(arr[ind].F+arr[ind].S), ind);
    }

    // cout << ans << " " << res << endl;
    cout << min(ans, res) << endl;
    
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:230:9: warning: unused variable 'j' [-Wunused-variable]
  230 |     int j = 1;
      |         ^

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