Submission #68773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68773	2018-08-18T10:56:31 Z	Inovak	Wiring (IOI17_wiring)	C++14	Compilation error	0 ms	0 KB

wiring

#include "wiring.h"
#include "grader.cpp"
#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;
    }

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

    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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:50:25: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.begin(), -inf);
                         ^~~~
wiring.cpp:51:26: warning: overflow in implicit constant conversion [-Woverflow]
     R.insert(R.end(), inf);
                          ^
wiring.cpp:52:25: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.begin(), -inf);
                         ^~~~
wiring.cpp:53:26: warning: overflow in implicit constant conversion [-Woverflow]
     B.insert(B.end(), inf);
                          ^
/tmp/ccGuPydx.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccADnmdR.o:wiring.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status