Submission #362737

#	Time	Username	Problem	Language	Result	Execution time	Memory
362737		alextodoran	Wiring (IOI17_wiring)	C++17	Compilation error	0 ms	0 KiB

wiring

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 200002;

const ll INF = LLONG_MAX / 2;

struct Node
{
    ll x;
    bool color;
};

bool operator < (const Node &a, const Node &b)
{
    return a.x < b.x;
}

int n;

Node v[N_MAX];

int prevL[N_MAX], prevR[N_MAX];
int L[N_MAX], R[N_MAX];

ll sumPref[N_MAX];

ll dp[N_MAX];

ll SGT1[N_MAX * 4], SGT2[N_MAX * 4];

void build (ll SGT[], int node, int l, int r)
{
    if(l == r)
    {
        SGT[node] = INF;
        return;
    }
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    build(SGT, lSon, l, mid);
    build(SGT, rSon, mid + 1, r);
    SGT[node] = min(SGT[lSon], SGT[rSon]);
}

void update (ll SGT[], int node, int l, int r, int upos, ll uval)
{
    if(l == r)
    {
        SGT[node] = uval;
        return;
    }
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    if(upos <= mid)
        update(SGT, lSon, l, mid, upos, uval);
    else
        update(SGT, rSon, mid + 1, r, upos, uval);
    SGT[node] = min(SGT[lSon], SGT[rSon]);
}

ll query (ll SGT[], int node, int l, int r, int ql, int qr)
{
    if(ql > qr)
        return INF;
    if(ql <= l && r <= qr)
        return SGT[node];
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    if(ql <= mid && mid + 1 <= qr)
        return min(query(SGT, lSon, l, mid, ql, qr), query(SGT, rSon, mid + 1, r, ql, qr));
    else if(ql <= mid)
        return query(SGT, lSon, l, mid, ql, qr);
    else
        return query(SGT, rSon, mid + 1, r, ql, qr);
}

ll min_total_length (vector <int> rv, vector <int> bv)
{
    for(int x : rv)
        v[++n] = Node{x, 0};
    for(int x : bv)
        v[++n] = Node{x, 1};
    sort(v + 1, v + n + 1);
    int currL = 1, currR = 0;
    v[n + 1].color = !v[n].color;
    for(int i = 1; i <= n + 1; i++)
    {
        if(i > 1 && v[i].color != v[i - 1].color)
        {
            for(int j = i - 1; j >= 1 && v[j].color == v[i - 1].color; j--)
            {
                L[j] = currL;
                R[j] = currR;
            }
            prevL[i] = currL;
            prevR[i] = currR;
            currL = i;
        }
        else
        {
            prevL[i] = prevL[i - 1];
            prevR[i] = prevR[i - 1];
        }
        currR = i;
    }
    for(int i = 1; i <= n; i++)
        sumPref[i] = sumPref[i - 1] + v[i].x;
    build(SGT1, 1, 1, n);
    build(SGT2, 1, 1, n);
    update(SGT1, 1, 1, n, 1, - v[R[1] + 1].x);
    update(SGT2, 1, 1, n, 1, - v[R[1]].x);
    for(int i = 1; i <= n; i++)
    {
        if(prevL[i] == 0)
            dp[i] = v[R[i] + 1].x * i - sumPref[i];
        else
        {
            int k = prevR[i];
            int l1 = prevL[i], r1 = min(prevR[i], 2 * k - i);
            int l2 = max(prevL[i], 2 * k - i + 1), r2 = prevR[i];
            dp[i] = min({INF,
                         query(SGT1, 1, 1, n, l1, r1) + sumPref[i] - 2 * sumPref[k] + v[k + 1].x * (2 * k - i + 1),
                         query(SGT2, 1, 1, n, l2, r2) + sumPref[i] - 2 * sumPref[k] - v[k].x * (i - 2 * k - 1)});
        }
        update(SGT1, 1, 1, n, i, dp[i - 1] + sumPref[i - 1] - v[R[i] + 1].x * i);
        update(SGT2, 1, 1, n, i, dp[i - 1] + sumPref[i - 1] - v[R[i]].x * i);
    }
    return dp[n];
}

int main()
{
	int n, m;
	assert(2 == scanf("%d %d", &n, &m));

	vector<int> r(n), b(m);
	for(int i = 0; i < n; i++)
		assert(1 == scanf("%d", &r[i]));
	for(int i = 0; i < m; i++)
		assert(1 == scanf("%d", &b[i]));

	long long res = min_total_length(r, b);
	printf("%lld\n", res);

	return 0;
}

Compilation message (stderr)

/tmp/ccJimUiO.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cckzGWbS.o:wiring.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status