Submission #137187

#	Time	Username	Problem	Language	Result	Execution time	Memory
137187		MAMBA	Wiring (IOI17_wiring)	C++17	100 / 100	272 ms	16948 KiB

wiring

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

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()

#define lid id<<1
#define rid lid|1

typedef long long ll;


const int N = 2e5 + 10;

ll seg[N << 2], lazy[N << 2];
int n;

void segAdd(int s, int t, ll val , int l = 0, int r = n, int id = 1) {
	if (l >= t || r <= s) return;
	if (l >= s && r <= t) {
		lazy[id] += val;
		seg[id] += val;
		return;
	}
	int mid = l + r >> 1;
	segAdd(s , t  ,val , l , mid , lid);
	segAdd(s , t ,val , mid , r , rid);
	seg[id] = min(seg[lid] , seg[rid]) + lazy[id];
}

ll segMin(int s, int t, int l = 0, int r = n ,int id = 1) {
	if (l >= t || r <= s) return 1e18;
	if (l >= s&& r <= t) return seg[id];
	int mid = l + r >> 1;
	return min(segMin(s , t , l , mid , lid) , segMin(s , t , mid , r , rid)) + lazy[id];
}


ll l[N], r[N], dp[N];

ll min_total_length(std::vector<int> R, std::vector<int> B) {

	memset(l , 0 , sizeof(l));
	memset(r , 0 , sizeof(r));

	n = R.size() + B.size();

	vector<ll> mg(n);

	merge(all(R) , all(B) , mg.begin());


	auto Tp = [&](int id) -> bool {
		return binary_search(all(R) , mg[id]);
	};

	{
		int last = 0;
		rep(i , 0 , n) {
			if (Tp(i) != Tp(last)) 
				last = i;
			l[i] = mg[i] - mg[last];
			if (i != last) l[i] += l[i - 1];
		}
	}

	{
		int last = n - 1;
		for (int i = n - 1; ~i; i--) {
			if (Tp(i) != Tp(last)) 
				last = i;
			if (last != n - 1) 
				r[i] = mg[last + 1] - mg[i];
			if (i != last) r[i] += r[i + 1];
		}
	}


	int a = 0, b = 0, c = 0;
	rep(i , 0 , n) {
		if (Tp(i) != Tp(b)) {
			c = a;
			a = b;
			b = i;
		}
		ll local = segMin(a , b);
		if (i == 0) local = 0;
		if (i != b) 
			local += l[i - 1];

		if (i == b && i) {
			local = min(local , segMin(c , a) + l[i - 1]);
		}

		local += r[i];

		dp[i] = local;

	//	cout << i << ' ' << local << endl;

		segAdd(i , i + 1, local);
		int pos = b - (i - b);
		pos = max(pos , a);
		if (pos != b)
			segAdd(pos , b , mg[b] - mg[b - 1]);
	}
	return segMin(a , b) + l[n - 1];



}

Compilation message (stderr)

wiring.cpp: In function 'void segAdd(int, int, ll, int, int, int)':
wiring.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
wiring.cpp: In function 'll segMin(int, int, int, int, int)':
wiring.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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