Submission #422286

#	Time	Username	Problem	Language	Result	Execution time	Memory
422286		timmyfeng	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	204 KiB

wiring

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

long long min_total_length(vector<int> r, vector<int> b) {
    vector<array<int, 2>> points;
    for (auto i : r) {
        points.push_back({i, -1});
    }
    for (auto i : b) {
        points.push_back({i, 1});
    }
    sort(points.begin(), points.end());

    int origin_slope = 0, min_slope = 0, max_slope = 0;
    int x_prv = 0, origin = 0;
    map<int, int> slopes;
    long long ans = 0;

    for (auto [x, t] : points) {
        slopes[origin] += 2 * (x - x_prv);
        origin_slope += x - x_prv;
        min_slope -= x - x_prv;
        max_slope += x - x_prv;
        x_prv = x;

        if (t == -1) {
            while (min_slope < 0) {
                auto it = slopes.begin();
                if (it->second > -min_slope) {
                    it->second += min_slope;
                    min_slope = 0;
                } else {
                    min_slope += it->second;
                    slopes.erase(it);
                }
            }
            origin_slope -= slopes[origin--];
            ans -= origin_slope;
        } else {
            while (max_slope > 0) {
                auto it = --slopes.end();
                if (it->second > max_slope) {
                    it->second -= max_slope;
                    max_slope = 0;
                } else {
                    max_slope -= it->second;
                    slopes.erase(it);
                }
            }
            ans += origin_slope;
            origin_slope += slopes[++origin];
        }
    }

    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45