Submission #48008

#	Time	Username	Problem	Language	Result	Execution time	Memory
48008		yusufake	Palembang Bridges (APIO15_bridge)	C++98	0 / 100	3 ms	808 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int maxnk = 310004;
ll dbuf[maxnk];
ll *d[maxnk];
vector<pii> coords;
vector<pii> v;

namespace Set {
int t[maxnk * 2];
int base = 1;

void init() {
    base = 1;
    while (base < sz(coords))
        base *= 2;
    fill(t, t + 2 * base, 0);
}

void put(int v, int val) {
    v += base;
    t[v] = val;
    while (v > 1) {
        v /= 2;
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}

int prev(int v) {
    v += base;
    while (true) {
        int u = v;
        v /= 2;
        if ((u & 1) && t[u] != t[v]) {
            v *= 2;
            break;
        }
    }
    while (v < base) {
        v *= 2;
        if (t[v + 1] > 0)
            ++v;
    }
    return v - base;
}

int next(int v) {
    v += base;
    while (true) {
        int u = v;
        v /= 2;
        if (!(u & 1) && t[u] != t[v]) {
            v = v * 2 + 1;
            break;
        }
    }
    while (v < base) {
        v *= 2;
        if (t[v] == 0)
            ++v;
    }
    return v - base;
}

}

namespace T {
int bl, br;
int pos;
ll f;

void init(int id) {
    Set::init();
    bl = id, br = id + 1;
    Set::put(v[id].first, 1);
    Set::put(v[id].second, 1);
    pos = v[id].second;
    f = coords[v[id].second].first - coords[v[id].first].first;
}

void move(int to) {
    f += (coords[to].first - coords[pos].first) * 2;
    pos = to;
}

void ins(int id) {
    //cerr << "ins " << id << '\n';
    int l = v[id].first;
    int r = v[id].second;
    Set::put(l, 1);
    Set::put(r, 1);
    f += abs(coords[r].first - coords[pos].first);
    f += abs(coords[l].first - coords[pos].first);
    if (pos < l)
        pos = Set::next(pos);
    else if (r < pos)
        move(Set::prev(pos));
}

void del(int id) {
    //cerr << "del " << id << '\n';
    int l = v[id].first;
    int r = v[id].second;
    if (pos <= l)
        pos = Set::prev(pos);
    else if (r <= pos)
        move(Set::next(pos));
    Set::put(l, 0);
    Set::put(r, 0);
    f -= abs(coords[r].first - coords[pos].first);
    f -= abs(coords[l].first - coords[pos].first);
}

void moveBounds(int nl, int nr) {
    //cerr << "move " << nl << ' ' << nr << '\n';
    assert(nl < nr);
    while (br < nr)
        ins(br++);
    while (bl > nl)
        ins(--bl);
    while (br > nr)
        del(--br);
    while (bl < nl)
        del(bl++);
    assert(bl == nl && br == nr);
}

} //T


int ck;
void divideAndConquer(int l, int r, int pl, int pr) {
    assert(T::bl == pl && T::br == l);
    int mid = (l + r) / 2;
    int pm = pl;
    T::moveBounds(pm, mid);
    pair<ll, int> best{T::f + d[ck][pm], pm};
    for (pm = pl + 1; pm < min(mid, pr); ++pm) {
        T::moveBounds(pm, mid);
        best = min(best, {T::f + d[ck][pm], pm});
    }
    d[ck + 1][mid] = best.first, pm = best.second;
    if (mid + 1 < r) {
        T::moveBounds(pm, mid + 1);
        divideAndConquer(mid + 1, r, pm, pr);
    }
    T::moveBounds(pl, l);
    if (l < mid)
        divideAndConquer(l, mid, pl, pm + 1);
}
long long ttt,nn;
char c1,c2;

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #else
    #endif
    int n, k;
    cin >> k >> n;
    forn (i, k + 1)
        d[i] = dbuf + i * (n + 1);
    vector<pii> _v;
    forn (i, n) {
        int l, r;
        cin >> c1 >> l >> c2 >> r;
        if (l > r)
            swap(l, r);
        if(c1 == c2) { ttt += r-l; continue; }
        ttt++;
        nn++;
        _v.emplace_back(l, r);
    }
    n = nn;
    sort(_v.begin(), _v.end(), [](pii a, pii b) {
                return a.first + a.second < b.first + b.second;
            });

    forn (i, n) {
        coords.emplace_back(_v[i].first, i * 2);
        coords.emplace_back(_v[i].second, i * 2 + 1);
    }
    sort(coords.begin(), coords.end());
    v.resize(n);
    forn (i, n) {
        v[i].first = lower_bound(coords.begin(), coords.end(),
            pii{_v[i].first, i * 2}) - coords.begin();
        v[i].second = lower_bound(coords.begin(), coords.end(),
            pii{_v[i].second, i * 2 + 1}) - coords.begin();
    }

    forn (i, k + 1)
        fill(d[i], d[i] + n + 1, infl);
    d[0][0] = 0;
    forn (j, k) {
        T::init(0);
        ck = j;
        divideAndConquer(1, n + 1, 0, n);
    }

    cout << ttt + d[k][n] << '\n';
}

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