Submission #367388

#	Time	Username	Problem	Language	Result	Execution time	Memory
367388		kig9981	Shortcut (IOI16_shortcut)	C++17	100 / 100	1683 ms	80892 KiB

shortcut

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const long long INF=0x7fffffffffffffffLL;
vector<pair<long long,int>> L, R;
int N, C, D[1000000];
long long PS[1000000];

void set_value(long long &x1, long long &y1, long long &x2, long long &y2, int x, int y, long long l)
{
	x1=max(x1,PS[x]+PS[y]-(l-D[x]-D[y]-C));
	y1=max(y1,PS[x]-PS[y]-(l-D[x]-D[y]-C));
	x2=min(x2,PS[x]+PS[y]+(l-D[x]-D[y]-C));
	y2=min(y2,PS[x]-PS[y]+(l-D[x]-D[y]-C));
}

bool solve(long long l)
{
	long long x1=-INF, y1=-INF, x2=INF, y2=INF, mv=INF, mv2=INF;
	int j=0, m=-1, m2=-1;
	for(int i=0;i<N;i++) {
		while(j<N && R[j].first>l+L[i].first) {
			int c=R[j++].second;
			if(PS[c]-D[c]<mv) {
				mv2=mv;
				mv=PS[c]-D[c];
				m2=m;
				m=c;
			}
			else if(PS[c]-D[c]<mv2) {
				mv2=PS[c]-D[c];
				m2=c;
			}
		}
		if(j==0 || j==1 && L[i].second==R[0].second || R[j-1].first<=l+L[i].first) continue;
		if(R[0].second==L[i].second) {
			if(R[1].first>l+L[i].first) set_value(x1,y1,x2,y2,L[i].second,R[1].second,l);
		}
		else if(R[0].first>l+L[i].first) set_value(x1,y1,x2,y2,L[i].second,R[0].second,l);
		set_value(x1,y1,x2,y2,L[i].second,(L[i].second==m ? m2:m),l);
	}
	if(x1>x2 || y1>y2) return false;
	for(int i=j=0;i<N;i++) {
		while(j<i && (PS[j]+PS[i]<x1 || PS[j]-PS[i]<y1)) j++;
		while(j>0 && (PS[j-1]+PS[i]>=x1 && PS[j-1]-PS[i]>=y1) && (PS[j]+PS[i]>x2 || PS[j]-PS[i]>y2)) j--;
		if(0<=j && j<i && PS[j]+PS[i]>=x1 && PS[j]-PS[i]>=y1 && PS[j]+PS[i]<=x2 && PS[j]-PS[i]<=y2) return true;
	}
	return false;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	int mx=d[0], mx2=0;
	long long s, e;
	N=n; C=c; L.emplace_back(-d[0],0); R.emplace_back(e=D[0]=d[0],0);
	for(int i=1;i<N;i++) {
		PS[i]=PS[i-1]+l[i-1];
		e+=D[i]=d[i];
		L.emplace_back(PS[i]-d[i],i);
		R.emplace_back(PS[i]+d[i],i);
		if(mx<d[i]) {
			mx2=mx;
			mx=d[i];
		}
		else if(mx2<d[i]) mx2=d[i];
	}
	s=mx+mx2; e+=PS[N-1];
	sort(L.rbegin(),L.rend());
	sort(R.rbegin(),R.rend());
	while(s<=e) {
		long long m=(s+e)>>1;
		if(solve(m)) e=m-1;
		else s=m+1;
	}
    return s;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool solve(long long int)':
shortcut.cpp:45:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |   if(j==0 || j==1 && L[i].second==R[0].second || R[j-1].first<=l+L[i].first) continue;
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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