Submission #46606

#	Time	Username	Problem	Language	Result	Execution time	Memory
46606		tieunhi	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	3 ms	912 KiB

bridge

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define maxc 1000000007

using namespace std;

int k, n, rr[2*N];
pii a[N];
long long f[2][N];

struct IntervalTree
{
    long long t[N << 3];
    int sz[N << 3];

    void build(int l, int r, int id)
    {
        t[id] = sz[id] = 0;
        if (l == r) return;
        int mid = (r + l)/2;
        build(l, mid, id*2);
        build(mid+1, r, id*2+1);
    }
    void update(int l, int r, int id, int x, int val)
    {
        if (l == r)
        {
            t[id] += val;
            sz[id]++;
            return;
        }
        int mid = (r + l)/2;
        if (x <= mid) update(l, mid, id*2, x, val);
        else update(mid+1, r, id*2+1, x, val);
        t[id] += val;
        sz[id]++;
    }
    int getpos(int l, int r, int id, int x)
    {
        if (l == r) return l;
        int mid = (r + l)/2;
        if (sz[id*2] >= x) return getpos(l, mid, id*2, x);
        return getpos(mid+1, r, id*2+1, x-sz[id*2]);
    }
    long long get(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return t[id];
        int mid = (r + l)/2;
        long long a = get(l, mid, id*2, x, y);
        long long b = get(mid+1, r, id*2+1, x, y);
        return a + b;
    }
    int getSz(int l, int r, int id, int x, int y)
    {
        if (l > y || r < x) return 0;
        if (l >= x && r <= y) return sz[id];
        int mid = (r + l)/2;
        int a = getSz(l, mid, id*2, x, y);
        int b = getSz(mid+1, r, id*2+1, x, y);
        return a + b;
    }
}t;

bool cmp(pii x, pii y)
{
    return x.F + x.S < y.F + y.S;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> k >> n;
    int cur = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        char x, y; int u, v;
        cin >> x >> u >> y >> v;
        if (x == y) ans += abs(u-v);
        else {
            if (u > v) swap(u, v);
            a[++cur] = mp(u, v);
        }
    }
    n = cur;
    sort(a+1, a+n+1, cmp);
    cur = 0;
    for (int i = 1; i <= n; i++)
    {
        rr[++cur] = a[i].F;
        rr[++cur] = a[i].S;
    }
    sort(rr+1, rr+cur+1);
    cur = unique(rr+1, rr+cur+1) - rr - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i].F = lower_bound(rr+1, rr+cur+1, a[i].F) - rr;
        a[i].S = lower_bound(rr+1, rr+cur+1, a[i].S) - rr;
    }
    for (int i = 1; i <= n; i++)
    {
        t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
        t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);

        int pos = t.getpos(1, 2*n, 1, i);
        long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
        long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
        f[0][i] = xx + yy;
    }
    t.build(1, 2*n, 1);
    for (int i = n; i >= 1; i--)
    {
        t.update(1, 2*n, 1, a[i].F, rr[a[i].F]);
        t.update(1, 2*n, 1, a[i].S, rr[a[i].S]);

        int pos = t.getpos(1, 2*n, 1, i);
        long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n);
        long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1);
        f[1][i] = xx + yy;
    }
    if (k == 1) cout <<f[0][n] + ans + n;
    else
    {
        long long res = maxc;
        for (int i = 0; i <= n; i++)
            res = min(res, ans + f[0][i] + f[1][i+1] + n);
        cout <<res;
    }
}

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