Submission #207049

#	Time	Username	Problem	Language	Result	Execution time	Memory
207049		mieszko11b	Shortcut (IOI16_shortcut)	C++14	100 / 100	1991 ms	85008 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
 
#define X first
#define Y second
 
int n, c;
ll d[1000007], x[1000007];
vector<pll> VP, VM;
 
//x[j] <= min(maxs - x[i], maxd + x[i])
//x[j] >= max(mins - x[i], mind + x[i])
 
bool find_pair(ll mins, ll maxs, ll mind, ll maxd) {
	for(int i = 1 ; i < n ; i++) {
		ll minv = max(mins - x[i], mind + x[i]);
		ll maxv = min(maxs - x[i], maxd + x[i]);
		auto it = lower_bound(x + i + 1, x + n + 1, minv);
		if(it != x + n + 1 && (*it) <= maxv)
			return true;
	}
	return false;
}
 
bool check(ll k) {
	ll mins = 0, maxs = 1e18, mind = 0, maxd = 1e18;
	ll minis = 1e18, maxis = 0;
	int ii = 0;
	for(int jj = 0 ; jj < n ; jj++) {
		int j = VP[jj].Y;
		while(ii < n && VM[ii].X + k < VP[jj].X) {
			int i = VM[ii].Y;
			minis = min(minis, x[i] + d[i]);
			maxis = max(maxis, x[i] + d[i]);
			ii++;
		}
		
		if(ii && 2 * d[j] <= k) {
			mins = max(mins, VP[jj].X + maxis - k + c);
			maxs = min(maxs, k - c + (x[j] - d[j]) + VM[0].X);
			mind = max(mind, VP[jj].X - VM[0].X - k + c);
			maxd = min(maxd, k - c + (x[j] - d[j]) - maxis);
		}
			//~ cout << k << " " <<minis << " " << maxis << " " << mins << " " << maxs << " " << mind << " " << maxd << endl;
 
	}
	
	for(int j = 1 ; j <= n ; j++) {
		if(2 * d[j] > k) {
			for(int i = 1 ; i < j ; i++) {
				if(x[i] - d[i] + k < x[j] + d[j]) {
					mins = max(mins, x[j] + d[j] + x[i] + d[i] - k + c);
					maxs = min(maxs, k - c + (x[j] - d[j]) + x[i] - d[i]);
					mind = max(mind, x[j] + d[j] - (x[i] - d[i]) - k + c);
					maxd = min(maxd, k - c + (x[j] - d[j]) - (x[i] + d[i]));					
				}
			}
		}
	}
	
	//~ cout << k << " " << mins << " " << maxs << " " << mind << " " << maxd << endl;
	return find_pair(mins, maxs, mind, maxd);
}
 
long long find_shortcut(int n, std::vector<int> l, std::vector<int> dd, int c) {
	d[1] = dd[0];
	::n = n;
	::c = c;
	for(int i = 1 ; i < n ; i++) {
		x[i + 1] = x[i] + l[i - 1];
		d[i + 1] = dd[i];
	}
		
	int max1 = 0, max2 = 0;
	for(int i = 1 ; i <= n ; i++) {
		VP.emplace_back(x[i] + d[i], i);
		VM.emplace_back(x[i] - d[i], i);
		if(d[i] >= max1) {
			max2 = max1;
			max1 = d[i];
		} else if(d[i] > max2)
			max2 = d[i];
	}
		
	sort(VP.begin(), VP.end());
	sort(VM.begin(), VM.end());
		
	ll a = max1 + max2, b = 1e18, mid;
	while(a < b) {
		mid = (a + b) / 2;
		if(check(mid))
			b = mid;
		else
			a = mid + 1;
	}
		
	return a;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 3 / 3