Submission #68778

#	Time	Username	Problem	Language	Result	Execution time	Memory
68778		Inovak	Wiring (IOI17_wiring)	C++14	100 / 100	107 ms	12500 KiB

wiring

//#include "grader.cpp"
#include "wiring.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define ll long long
#define OK puts("OK");
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 5e5+10;
const int nn = 2e5;
const ll inf = 1e16+7;

ll n, m, x, b;
ll dp[N], sum[N];
ll pr[N];
vector <pair <ll, ll> > all;

ll get(int l, int r) {
    return abs(sum[r] - sum[l - 1]);
}

long long min_total_length(vector<int> R, vector<int> B) {
    n = sz(R);
    m = sz(B);
    for(int i = 0; i < n; i++) {
        all.pb(mk(R[i], 1));
        dp[i+1] = inf;
    }
    for(int i = 0; i < m; i++) {
        all.pb(mk(B[i], 0));
        dp[i + n + 1] = inf;
    }
    //sort(all(R));
    //sort(all(B));

    if(R[n - 1] < B[0]) {
        ll ans = 0;
        for(int i = 0; i < n - 1; i++)
            ans += abs(R[n - 1] - R[i]);
        for(int i = 1; i < sz(B); i++)
            ans += abs(B[i] - B[0]);
        return ans + max(n, m) * (B[0] - R[n - 1]);
    }

    R.insert(R.begin(), -inf);
    R.insert(R.end(), inf);
    B.insert(B.begin(), -inf);
    B.insert(B.end(), inf);

    n += m;
    all.pb(mk(-inf, -1));
    sort(all(all));
    memset(pr, -1, sizeof(pr));
    pr[nn] = 0;

    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (all[i].sc ? -all[i].fr : all[i].fr);
        b += (all[i].sc ? -1 : 1);
        int j = pr[b + nn];
        pr[b + nn] = i;

        ll nl, nr;
        if (all[i].sc) {
            nl = *(lower_bound(B.begin(), B.end(), all[i].first) - 1);
            nr = *lower_bound(B.begin(), B.end(), all[i].first);
        }
        else {
            nl = *(lower_bound(R.begin(), R.end(), all[i].first) - 1);
            nr = *lower_bound(R.begin(), R.end(), all[i].first);
        }
        dp[i] = dp[i - 1] + min(all[i].first - nl, nr - all[i].first);

        if(j == -1) continue;
        dp[i] = min(dp[i], dp[j] + get(j + 1, i));
    }
    return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:52:25: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.begin(), -inf);
                         ^~~~
wiring.cpp:53:26: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.end(), inf);
                          ^
wiring.cpp:54:25: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.begin(), -inf);
                         ^~~~
wiring.cpp:55:26: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.end(), inf);
                          ^

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