Submission #839818

#	Time	Username	Problem	Language	Result	Execution time	Memory
839818		popovicirobert	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	1614 ms	40632 KiB

bridge

#include <bits/stdc++.h>
 
using namespace std;

constexpr long long INF = 1e18;
constexpr int MAXC = (int) 1e9;

struct SegTree {
    SegTree(int n) {
        data.resize(4 * n + 1);
    }

    void update(int node, int left, int right, int pos, long long value) {
        if (left == right) {
            data[node].first += value;
            data[node].second++;
        } else {
            int mid = (left + right) / 2;
            if (pos <= mid) update(2 * node, left, mid, pos, value);
            else update(2 * node + 1, mid + 1, right, pos, value);
            data[node].first = data[2 * node].first + data[2 * node + 1].first;
            data[node].second = data[2 * node].second + data[2 * node + 1].second;
        }
    }

    pair<long long, int> query(int node, int left, int right, int ql, int qr) {
        if (ql > qr) {
            return {0, 0};
        }

        if (ql <= left && right <= qr) {
            return data[node];
        } else {
            int mid = (left + right) / 2;
            pair<long long, int> L = {0, 0}, R = {0, 0};
            if (ql <= mid) L = query(2 * node, left, mid, ql, qr);
            if (mid < qr) R = query(2 * node + 1, mid + 1, right, ql, qr);
            return {L.first + R.first, L.second + R.second};
        }
    }

    vector<pair<long long, int>> data;
};


struct Road {
    int x, y;
};

auto normalize(const vector<Road>& roads) {
    vector<int> v;
    for (auto& road : roads) {
        v.push_back(road.x);
        v.push_back(road.y);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());

    unordered_map<int, int> norm;
    for (int i = 0; i < (int)v.size(); i++) {
        norm[v[i]] = i + 1;
    }
    return norm;
}

void GetAnswers(vector<long long>& pref, vector<Road>& roads) {
    int n = (int)roads.size() - 1;
    for (int i = 1; i <= n; i++) {
        if (roads[i].x > roads[i].y) {
            swap(roads[i].x, roads[i].y);
        }
        // cerr << roads[i].x << " " << roads[i].y << "    ";
    }

    // cerr << "\n";

    pref.resize(n + 1, INF);
    pref[0] = 0;

    auto norm = normalize(roads);
    const int MAX_VALUE = norm.size();

    vector<int> realValue(MAX_VALUE + 1);
    for (const auto& p : norm) {
        realValue[p.second] = p.first;
    }
    
    SegTree small(MAX_VALUE), large(MAX_VALUE);

    auto GetSplit = [&](int split) {
        auto SMALL = small.query(1, 1, MAX_VALUE, 1, split - 1);
        auto LARGE = large.query(1, 1, MAX_VALUE, split + 1, MAX_VALUE);
        return 2LL * realValue[split] * SMALL.second - SMALL.first + 
               LARGE.first - 2LL * realValue[split] * LARGE.second;
    };

    long long totalDiffSum = 0;
    for (int i = 1; i <= n; i++) {
        long long diff = roads[i].y - roads[i].x;
        totalDiffSum += diff;
        small.update(1, 1, MAX_VALUE, norm[roads[i].y], roads[i].x + roads[i].y + diff);
        large.update(1, 1, MAX_VALUE, norm[roads[i].x], roads[i].x + roads[i].y - diff);

        int split = 0;
        for (int step = 1 << 17; step; step >>= 1) {
            if (split + step < MAX_VALUE && GetSplit(split + step) >= GetSplit(split + step + 1)) {
                split += step;
            }
        }
        pref[i] = GetSplit(split + 1) + totalDiffSum + i;
        // cerr << realValue[split + 1] << " " << pref[i] << "\n";
    }
}

 
int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int k, n;
    cin >> k >> n;

    vector<Road> roads(1);
    long long sameSideAnswer = 0;

    for (int i = 1; i <= n; i++) {
        char side1, side2;
        int x, y;

        cin >> side1 >> x >> side2 >> y;

        if (side1 == side2) {
            sameSideAnswer += llabs(x - y);
        } else {
            roads.push_back({x, y});
        }
    }

    n = (int)roads.size() - 1;
    sort(roads.begin() + 1, roads.end(), [](const Road& r1, const Road& r2) {
        return r1.x + r1.y < r2.x + r2.y;
    });

    vector<long long> pref;
    GetAnswers(pref, roads);

    vector<long long> suff;
    for (int i = 1; i < n - i + 1; i++) {
        swap(roads[i], roads[n - i + 1]);
    }
    for (int i = 1; i <= n; i++) {
        auto& road = roads[i];
        road.x = MAXC - road.x;
        road.y = MAXC - road.y;
    }
    GetAnswers(suff, roads);

    long long differentSideAnswer = pref[n];
    if (k == 2) {
        for (int i = 0; i <= n; i++) {
            differentSideAnswer = min(differentSideAnswer, pref[i] + suff[n - i]);
        }
    }

    cout << sameSideAnswer + differentSideAnswer << "\n";
 
    return 0;
}

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