Submission #1215673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215673		zhenja	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	183 ms	327680 KiB

bridge

#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;

# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
    return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
    return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937 mt(time(0));
const int N = 1e5 + 2, inf = 1e9 + 100, mod = 1e9 + 7, mod2 = 998244353, P = 257;
const ll llinf = 1e18 + 1000;
struct st {
    int a, b;
};
bool cmp(st a, st b) {
    return a.a + a.b < b.a + b.b;
}
vector<int> sz;
struct segtree {
    struct node {
        ll sum;
        int cnt;
        node() : sum(0), cnt(0) {}
        node operator+(node a) {
            node ans;
            ans.sum = sum + a.sum;
            ans.cnt = cnt + a.cnt;
        }
    };
    node t[N * 4];
    segtree() {
        fill(t, t + N * 4, node());
    }
    void upd(int v, int l, int r, int i, int val) {
        t[v].sum += sz[i] * val;
        t[v].cnt += val;
        if (r - l == 1) return;
        int m = (l + r) >> 1;
        if (i < m) upd(v + 1, l, m, i, val);
        else
            upd(v + 2 * (m - l), m, r, i, val);
    }
    void upd(int i, int val) {
        upd(0, 0, sz.size(), i, val);
    }
    ll get(int v, int l, int r, int k) {
        if (r - l == 1) {
            return 1ll * sz[l] * (t[v].cnt - k) - 1ll * sz[l] * k;
        }
        int m = (l + r) >> 1;
        if (t[v + 1].cnt <= k) return get(v + 2 * (m - l), m, r, k - t[v + 1].cnt) - t[v + 1].sum;
        else
            return get(v + 1, l, m, k) + t[v + 2 * (m - l)].sum;
    }
    ll get() {
        return get(0, 0, sz.size(), t[0].cnt / 2);
    }
};

void solve() {
    int n, k;
    cin >> k >> n;
    vector<st> a;
    ll add = 0;
    for (int i = 0; i < n; ++i) {
        char c1, c2;
        int x1, x2;
        cin >> c1 >> x1 >> c2 >> x2;
        if (c1 != c2) {
            a.push_back({ x1, x2 });
            sz.push_back(x1);
            sz.push_back(x2);
        }
        else {
            add += abs(x1 - x2);
        }
    }
    n = a.size();
    sort(all(a), cmp);
    sort(all(sz));
    sz.erase(unique(all(sz)), sz.end());
    for (int i = 0; i < n; ++i) {
        a[i].a = lower_bound(all(sz), a[i].a) - sz.begin();
        a[i].b = lower_bound(all(sz), a[i].b) - sz.begin();
    }
    ll ans = llinf;
    segtree t1, t2;
    for (int i = 0; i < n; ++i) {
        t2.upd(a[i].a, 1);
        t2.upd(a[i].b, 1);
    }
    ans = t2.get();
    if (k == 1) {
        cout << ans + add + n;
        return;
    }
    for (int i = 0; i < n; ++i) {
        t1.upd(a[i].a, 1);
        t1.upd(a[i].b, 1);
        t2.upd(a[i].a, -1);
        t2.upd(a[i].b, -1);
        ans = min(ans, t1.get() + t2.get());
    }
    cout << ans + add + n;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("coloring.in", "r", stdin);
    //freopen("coloring.out", "w", stdout);

    //ld time1 = clock();

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
        cout.flush();
    }

    //ld time2 = clock();
    //cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
    return 0;
}

Compilation message (stderr)

bridge.cpp: In member function 'segtree::node segtree::node::operator+(segtree::node)':
bridge.cpp:63:9: warning: no return statement in function returning non-void [-Wreturn-type]
   63 |         }
      |         ^

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