Submission #870536

#	Time	Username	Problem	Language	Result	Execution time	Memory
870536		Lib	Shortcut (IOI16_shortcut)	C++14	93 / 100	2057 ms	382120 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
long long lim=1000000000000000000;
long long BoundTopLeft,BoundTopRight,BoundBottomLeft,BoundBottomRight; //Where the lines that forms the current bound cuts the X-axis
long long TopLeft,TopRight,BottomLeft,BottomRight; //Where the lines that forms the current square cuts the Y-axis
int n;
long long Mainline[1000003];
long long Secondline[1000003];
long long Extraline;
long long C,X,Y;
long long Sum[1000003];
long long Diff[1000003];
long long Curmin,CurMaxsum,MaxSumIndex,CurMindiff;
long long TreeDiameter=0;
vector <int> Dominators;
deque <int> DominatorsEnableQueue;
deque <int> MinDiffIndex;
stack <int> temp;
vector <stack<int> > EnterSquareMakingOrgy;
int P1,P2,P3,P4;
int ok;
struct NewOrder{
	int ID;
	int NextDominatorID;
};
bool operator< (const NewOrder &x, const NewOrder &y){
	return Diff[x.ID]<Diff[y.ID];
}
NewOrder SortedByDiff[1000003];
long long PossibleDiameter(long long Dist){ 
	BoundTopLeft=-lim;
	BoundTopRight=lim;
	BoundBottomLeft=-lim;
	BoundBottomRight=lim;
	int k;
	MinDiffIndex.clear();
	k=1;
	for(int i=1;i<=n;i++){
		if(!MinDiffIndex.empty()){
			k=MinDiffIndex.back();
			C=Dist-(Extraline+Secondline[i]+Secondline[k]);
			X=Mainline[i];
			Y=Mainline[k];
			TopLeft=X-C-Y;
			TopRight=X+C+Y;
			BottomLeft=X-C+Y; 
			BottomRight=X+C-Y; 
			if((Secondline[i]+Secondline[k]+Mainline[i]-Mainline[k])>Dist){
			BoundTopLeft=max(BoundTopLeft,TopLeft);
			BoundTopRight=min(BoundTopRight,TopRight);
			BoundBottomRight=min(BoundBottomRight,BottomRight);
			BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
			}
		}
		if(i==1||Diff[i]<Diff[MinDiffIndex.back()]){
			MinDiffIndex.push_back(i);
		}
	}
	
	k=1;
	EnterSquareMakingOrgy.clear();
	for(int i=0;i<=Dominators.size()+1;i++){
		EnterSquareMakingOrgy.push_back(temp);
	}
	CurMaxsum=-lim;
	int Pointer=1;
	MaxSumIndex=1;
	for(int i=2;i<Dominators.size();i++){
		while(Pointer<=n&&Sum[Dominators[i]]-Diff[SortedByDiff[Pointer].ID]>Dist){
			EnterSquareMakingOrgy[max(i,SortedByDiff[Pointer].NextDominatorID)].push(SortedByDiff[Pointer].ID);
				Pointer++;
		}
		while(!EnterSquareMakingOrgy[i].empty()){
			if(CurMaxsum<Sum[EnterSquareMakingOrgy[i].top()]){
				CurMaxsum=Sum[EnterSquareMakingOrgy[i].top()];
				MaxSumIndex=EnterSquareMakingOrgy[i].top();
			}
			EnterSquareMakingOrgy[i].pop();
		}
			k=MaxSumIndex;
			C=Dist-(Extraline+Secondline[Dominators[i]]+Secondline[k]);
			X=Mainline[Dominators[i]];
			Y=Mainline[k];
			TopLeft=X-C-Y;
			TopRight=X+C+Y;
			BottomLeft=X-C+Y; 
			BottomRight=X+C-Y; 
			if((Secondline[Dominators[i]]+Secondline[k]+Mainline[Dominators[i]]-Mainline[k])>Dist){
			BoundTopLeft=max(BoundTopLeft,TopLeft);
			BoundTopRight=min(BoundTopRight,TopRight);
			BoundBottomRight=min(BoundBottomRight,BottomRight);
			BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
			}
	}
	if(BoundTopLeft>BoundBottomRight||BoundBottomLeft>BoundTopRight){
		return 0;
	}
	P1=1;
	P2=n+1;
	P3=1;
	P4=n+1;
	ok=0;
	while(Mainline[P1]<BoundTopLeft&&P1<=n){
		P1++;
	}
	while(Mainline[P3]<BoundBottomLeft&&P3<=n){
		P3++;
	}
	while(Mainline[P2]>BoundBottomRight&&P2>1){
		P2--;
	}
	while(Mainline[P4]>BoundTopRight&&P4>1){
		P4--;
	}
	 if(P1<=P2&&P3<=P4){
	    if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
	        ok=1;
	        return ok;
	    }
		}
	for(int i=2;i<=n;i++){
	    while(Mainline[P1]-Mainline[i]<BoundTopLeft&&P1<=n){
	        P1++;
	    }
	    while(Mainline[P2+1]-Mainline[i]<=BoundBottomRight&&P2<=n){
	        P2++;
	    }
	    while(Mainline[i]+Mainline[P3-1]>=BoundBottomLeft&&P3>1){
	        P3--;
	    }
	    while(Mainline[i]+Mainline[P4]>BoundTopRight&&P4>=1){
	        P4--;
	    }
	    if(P1<=P2&&P3<=P4){
	    if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
	        ok=1;
	        return ok;
	    }
		}else{
			continue;
		}
	}
		return ok;
}
long long find_shortcut(int N, vector <int> L, vector <int> D, int C){
	n=N;
	Extraline=C;
	long long temp=0;
	for(int i=2;i<=n;i++){
		temp=L[i-2];
		Mainline[i]=Mainline[i-1]+temp;
	}
	Mainline[n+1]=lim;
	Curmin=lim;
	CurMindiff=lim;
	for(int i=1;i<=n;i++){
		Secondline[i]=D[i-1];
		Sum[i]=Mainline[i]+Secondline[i];
		Diff[i]=Mainline[i]-Secondline[i];
		if(i>=2){
			TreeDiameter=max(TreeDiameter,Sum[i]-CurMindiff);
		}
		CurMindiff=min(CurMindiff,Diff[i]);
	}
	long long l=1,r=TreeDiameter;
	Dominators.clear();
	Dominators.push_back(0);
	for(int i=1;i<=n;i++){
		if(Sum[i]>Sum[Dominators.back()]){
			Dominators.push_back(i);
		}
		SortedByDiff[i]={i,Dominators.size()};
	}
	sort(SortedByDiff+1,SortedByDiff+n+1);
	long long mid;
	while(r-l>1){
		mid=(r+l)/2;
		if(PossibleDiameter(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(PossibleDiameter(l)){
		return l;
	}else if(PossibleDiameter(r)){
		return r;
	}
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int PossibleDiameter(long long int)':
shortcut.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i=0;i<=Dominators.size()+1;i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~
shortcut.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=2;i<Dominators.size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:173:37: warning: narrowing conversion of 'Dominators.std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  173 |   SortedByDiff[i]={i,Dominators.size()};
      |                      ~~~~~~~~~~~~~~~^~
shortcut.cpp:190:1: warning: control reaches end of non-void function [-Wreturn-type]
  190 | }
      | ^

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