Submission #388600

#	Time	Username	Problem	Language	Result	Execution time	Memory
388600		alishahali1382	Shortcut (IOI16_shortcut)	C++14	97 / 100	2080 ms	92220 KiB

shortcut

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

const ll INF=10000001000000000ll;
const int MAXN=1000010;

int n, m, k;
ll L[MAXN], D[MAXN], X[MAXN], C, ans;
pli XD[MAXN]; // X-D
pli DX[MAXN]; // D+X
ll X1, Y1, X2, Y2;

bool Check(ll val){
	X1=Y1=-INF;
	X2=Y2=INF;
	pli mn1={INF, 0}, mn2={INF, 0};
	pli mx1={-INF, 0}, mx2={-INF, 0};
	int jj=1;
	for (int ii=1; ii<=n; ii++){
		int i=DX[ii].second;
		while (jj<=n && DX[ii].first-val>XD[jj].first){
			int j=XD[jj++].second;
			pli p={X[j]+D[j], j};
			if (p>mx1) swap(mx1, p);
			if (p>mx2) swap(mx2, p);
			
			p={X[j]-D[j], j};
			if (p<mn1) swap(mn1, p);
			if (p<mn2) swap(mn2, p);
		}
		// if (D[i]+X[i]-val<=(X[j]-D[j])) continue ;
		ll mx=(mx1.second==i?mx2.first:mx1.first);
		ll mn=(mn1.second==i?mn2.first:mn1.first);
		X1=max(X1, +X[i]-val+C+D[i] +mx);
		Y1=max(Y1, -X[i]-val+C+D[i] +mx);
		X2=min(X2, +X[i]+val-C-D[i] +mn);
		Y2=min(Y2, -X[i]+val-C-D[i] +mn);
		// AddRect(x+y-z, x-y-z, x+y+z, x-y+z);
	}
	for (int i=1; i<=n; i++){
		ll y=X[i];
		ll l=max(X1-y, Y1+y), r=min(X2-y, Y2+y);
		int pos=lower_bound(X+1, X+n+1, l)-X;
		if (pos<=n && X[pos]<=r) return 1;
	}
	return 0;
}

ll find_shortcut(int _n, vector<int> l, vector<int> d, int _C){
	n=_n;
	C=_C;
	for (int i=1; i<n; i++) L[i]=l[i-1], X[i+1]=X[i]+L[i];
	for (int i=1; i<=n; i++){
		D[i]=d[i-1];
		XD[i]={X[i]-D[i], i};
		DX[i]={D[i]+X[i], i};
	}
	sort(XD+1, XD+n+1);
	sort(DX+1, DX+n+1);

	ll dwn=-1, up=INF;
	while (up-dwn>1){
		ll mid=(dwn+up)>>1;
		if (Check(mid)) up=mid;
		else dwn=mid;
	}
	return up;
}

• 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: 0 / 3