Submission #49013

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49013	2018-05-21T08:12:54 Z	polyfish	Wiring (IOI17_wiring)	C++14	Compilation error	0 ms	0 KB

wiring

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';

const int maxn = 200002;
const int64_t inf = 1e18;

struct rmq {
	int n;
	int64_t container[maxn*4];

	void init(int _n) {
		n = _n;
		for (int i=0; i<=4*n; ++i)
			container[i] = inf;
	}

	void update(int pos, int val, int l, int r, int id) {
		if (pos<l || pos>r)
			return;
		if (l==pos && pos==r) {
			container[id] = val;
			return;
		}
		int mid = (l+r)/2;
		update(pos, val, l, mid, id*2);
		update(pos, val, mid+1, r, id*2+1);
		container[id] = max(container[id*2], container[id*2+1]);
	}

	int64_t get(int u, int v, int l, int r, int id) {
		if (v<l || u>r)
			return inf;
		if (u<=l && r<=v)
			return container[id];
		int mid = (l+r)/2;
		return min(get(u, v, l, mid, id*2),
					get(u, v, mid+1, r, id*2+1));
	}

	void update(int pos, int val) {
		update(pos, val, 1, n, 1);
	}

	int64_t get(int u, int v) {
		return get(u, v, 1, n, 1);
	}
};

int m, n, L[maxn], R[maxn], pos[maxn];
pair<int, int> a[maxn];
int64_t f[maxn], ps[2][maxn];

void enter() {
	cin >> m >> n;
	for (int i=1; i<=m; ++i) {
		int x; cin >> x;
		a[i] = make_pair(x, 0);
	}
	for (int i=1; i<=n; ++i) {
		int x; cin >> x;
		a[m+i] = make_pair(x, 1);
	}
}

void init() {
	n = m+n;
	sort(a+1, a+n+1);
	int cnt = 0;
	for (int i=1; i<=n+1; ++i) {
		if (i==1 || i==n+1 || a[i].second!=a[i-1].second) {
			++cnt;
			L[cnt] = i;
			R[cnt-1] = i-1;
		}
		pos[i] = cnt;
	}
	for (int i=1; i<=n; ++i) {
		for (int j=0; j<2; ++j)
			ps[j][i] = ps[j][i-1] + (a[i].second==j ? a[i].first : 0);
	}
}

int main() {
	//freopen("wiring.inp", "r", stdin);
	//freopen("wiring.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	init();
	for (int i=1; i<=n; ++i) {
		f[i] = inf;
		if (pos[i]==1)
			continue;
		int w = 0, b = 1;
		if (a[i].second==1)
			swap(w, b);
		int l = L[pos[i]-1], r = R[pos[i]-1];
		for (int j=l; j<=r; ++j) {
			int64_t cost;
			if (i==L[pos[i]])
				cost = 1LL*(i-j)*a[i].first - (ps[b][i] - ps[b][j-1]);
			else if (j==R[pos[j]])
				cost = (ps[w][i] - ps[w][j-1]) - 1LL*(i-j)*a[j].first;
			else {
				cost = (ps[w][i]-ps[w][j-1]) - (ps[b][i]-ps[b][j-1]);
				//if (i==6 && j==3)
				//	debug(a[i].first-a[j].first);
				if (i-L[pos[i]]+1>R[pos[j]]-j+1)
					cost += 1LL*(i-L[pos[i]]-R[pos[j]]+j)*a[L[pos[i]]].first;
				else 
					cost += 1LL*(R[pos[j]]-j-i+L[pos[i]])*a[R[pos[j]]].first;
			}
			f[i] = min(f[i], f[j-1] + cost);
		}
	}
	//PR(f, n);
	cout << f[n];
}

Compilation message

/tmp/cck6uNw2.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccuBeF0E.o:wiring.cpp:(.text.startup+0x0): first defined here
/tmp/cck6uNw2.o: In function `main':
grader.cpp:(.text.startup+0x23b): undefined reference to `min_total_length(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status