Submission #704170

#	Time	Username	Problem	Language	Result	Execution time	Memory
704170		Abrar_Al_Samit	Wiring (IOI17_wiring)	C++17	100 / 100	121 ms	26772 KiB

wiring

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

const long long INF = 1e18;
const int nax = 1e5 + 2;
vector<int>pos;
vector<int>type;
int upto[nax * 2];

template<const int N> struct segmentTree {
	long long st[N * 4];

	segmentTree() {
		fill(st, st+N*4, INF);
	}
	void update(int l, int r, int pos, long long val, int v) {
		if(l==r) {
			st[v] = val;
			return;
		}
		int mid = (l+r)/2;
		if(pos<=mid) update(l, mid, pos, val, v*2);
		else update(mid+1, r, pos, val, v*2+1);

		st[v] = min(st[v*2], st[v*2+1]);
	}
	long long query(int l, int r, int L, int R, int v) {
		if(l>=L && r<=R) return st[v];
		if(l>R || r<L) return INF;

		int mid = (l+r)/2;
		return min(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
	}
}; segmentTree<nax * 2>lefBig, lefSmall;

long long min_total_length(vector<int> r, vector<int> b) {
	int p0 = 0, p1 = 0;
	int n = r.size(), m = b.size();

	while(p0<n || p1<m) {
		if(p0<n && p1<m) {
			if(r[p0]<b[p1]) {
				pos.push_back(r[p0]);
				type.push_back(0);
				++p0;
			} else {
				pos.push_back(b[p1]);
				type.push_back(1);
				++p1;
			}
		} else if(p0<n) {
			pos.push_back(r[p0]);
			type.push_back(0);
			++p0;
		} else {
			pos.push_back(b[p1]);
			type.push_back(1);
			++p1;
		}
	}
	fill(upto, upto+nax*2, n+m-1);
	long long rit1[n+m], rit2[n+m], lef1[n+m], lef2[n+m];
	for(int i=0; i<n+m; ++i) {
		int j = i;
		while(j+1<n+m && type[j+1]==type[i]) ++j;
		
		int pt = j;
		long long cr = 0;
		while(j>=i) cr += pos[pt] - pos[j], rit1[j] = cr, upto[j] = pt, --j;

		j = pt;
		cr = 0;
		while(j>=i) {
			cr += (pt+1<n+m) ? pos[pt+1] - pos[j] : INF;
			cr = min(cr, INF);
			rit2[j] = cr;
			--j;
		}
		i = pt;
	}


	for(int i=n+m-1; i>=0; --i) {
		int j = i;
		while(j-1>=0 && type[j-1]==type[i]) --j;

		int pt = j;
		long long cr = 0;
		while(j<=i) cr += pos[j] - pos[pt], lef1[j] = cr, ++j;

		cr = 0;
		j = pt;
		while(j<=i) {
			cr += (pt-1>=0) ? pos[j] - pos[pt-1] : INF;
			cr = min(cr, INF);
			lef2[j] = cr;
			++j;
		}
		i = pt;
	}


	lefBig.update(1, n+m, n+m, lef1[n+m-1], 1);
	lefSmall.update(1, n+m, n+m, lef2[n+m-1], 1);

	vector<long long>dp(n+m, INF);
	for(int i=n+m-1; i>=0; --i) {
		if(upto[i]==n+m-1) continue;

		int leflen = upto[i] - i + 1;
		int j = upto[i] + leflen;
		j = (upto[i]==n+m-1) ? n+m : min(j, upto[upto[i]+1]);

		dp[i] = rit2[i] + lefBig.query(1, n+m, upto[i]+2, j+1, 1);

		int k = min(n+m, upto[upto[i]+1]);

		dp[i] = min(dp[i], rit1[i] + lefSmall.query(1, n+m, j+2, k+1, 1));

		if(i) {
			lefBig.update(1, n+m, i+1, min(INF, min(dp[i], dp[i+1]) + lef1[i]), 1);
			lefSmall.update(1, n+m, i+1, min(INF, min(dp[i], dp[i+1]) + lef2[i]), 1);
		}
	}
	return dp[0];
}

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