E. Byteland, Berland and Disputed Cities | Educational Codeforces Round 42 (Rated for Div. 2)

とりあえず、頂点を座標の昇順に並べておく。以下のように構成できる。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    vll b, r, p, xs;
    rep(i, n) {
        ll x;
        cin >> x;
        char c;
        cin >> c;
        if (c == 'B')b.push_back(x);
        if (c == 'R')r.push_back(x);
        if (c == 'P')p.push_back(x);
    }

    sort(all(b));
    sort(all(r));
    sort(all(p));

    ll ans = 0;

    if (sz(p) == 0) {
        ans += !sz(b) ? 0 : b.back() - b[0];
        ans += !sz(r) ? 0 : r.back() - r[0];
    } else {
        if (sz(b) && b[0] < p[0])ans += p[0] - b[0];
        if (sz(r) && r[0] < p[0])ans += p[0] - r[0];
        if (sz(b) && b.back() > p.back())ans += b.back() - p.back();
        if (sz(r) && r.back() > p.back())ans += r.back() - p.back();
        int bL = 0, bR = 0, rL = 0, rR = 0;
        rep(i, sz(p) - 1) {
            ll low = p[i], high = p[i + 1];
            while (bL < sz(b) && b[bL] <= low)bL++;
            while (rL < sz(r) && r[rL] <= low)rL++;
            while (bR < sz(b) && b[bR] < high)bR++;
            while (rR < sz(r) && r[rR] < high)rR++;
            int bN = bR - bL, rN = rR - rL;

            if (bN > 0 && rN > 0) {
                ll u = 3 * (high - low);
                ll v = 2 * (high - low);
                ll bM = max(b[bL] - low, high - b[bR - 1]);
                ll rM = max(r[rL] - low, high - r[rR - 1]);
                FOR(j, bL, bR - 1)smax(bM, b[j + 1] - b[j]);
                FOR(j, rL, rR - 1)smax(rM, r[j + 1] - r[j]);
                u -= bM + rM;
                ans += min(u, v);
            } else if (bN > 0) {
                ll bM = max(b[bL] - low, high - b[bR - 1]);
                FOR(j, bL, bR - 1)smax(bM, b[j + 1] - b[j]);
                ans += 2 * (high - low) - bM;
            } else if (rN > 0) {
                ll rM = max(r[rL] - low, high - r[rR - 1]);
                FOR(j, rL, rR - 1)smax(rM, r[j + 1] - r[j]);
                ans += 2 * (high - low) - rM;
            } else {
                ans += high - low;
            }
        }
    }

    cout << ans << endl;
}