#include <bits/stdc++.h>
#include "shortcut.h"
#define int long long
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O2")
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[1100003];
long long Secondline[1100003];
long long Extraline;
long long C,X,Y;
long long Sum[1100003];
long long Diff[1100003];
long long Curmin,CurMaxsum,MaxSumIndex,CurMindiff;
long long TreeDiameter=0;
vector <int> Dominators;
deque <int> MinDiffIndex;
stack <int> TStack;
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[1100003];
long long PossibleDiameter(long long Dist){
BoundTopLeft=-lim;
BoundTopRight=lim;
BoundBottomLeft=-lim;
BoundBottomRight=lim;
int k;
/*
From the constrains, it is obvious that we'll now have to finish both the Bound-creating process and checking whether a valid connection exists in O(N) per binary search iteration.
This means, we'll have to create not too many (precisely no more than 2N) squares, and checking whether a valid connection exists in linear time.
*/
/*
From now on, we will refer to Mainline[i]+Secondline[i] as Sum[i] and Mainline[i]-Secondline[i] as Diff[i]
Notice that not all squares are necessary: As we only cares about the Rightmost TopLeft, Rightmost BottomLeft, Leftmost BottomRight, Leftmost TopRight bound among all squares,
for all squares that we can create from combining station j with some station i<j (of course they'll have to satisfy Sum[j]-Dist[i]>Dist first), we will only need to care
about the square with the rightmost TopLeft and the other square with the leftmost BottomRight formed by combining station j with some station i (which is, 2 squares at most for each j)
(rightmost TopLeft: When we respresent the topleft bound of this square as the graph of x-y=a, this is the one with highest a.
leftmost BottomRight: Same, but lowest a.
*/
//We will handle the "Rightmost TopLeft square" and "Leftmost BottomRight square" quite differently, as creating rightmost squares are a lot easier than creating leftmost squares.
//Phase 1: Creating all Rightmost Topleft squares, and merging them together.
/*
A "Rightmost Topleft square" formed by station j is the square that is formed by the inequations required for station j to be able to reach station i (i<j), and Sum[j]-Diff[i]>Dist, and
the x-y value of the line that overlaps with its TopLeft bound is the highest among all squares formed by station j.
This square has to satisfy 2 inequations:
1) Sum[j]-Diff[i]>Dist (so that the square is "valid"
2) Mainline[j]-(Dist-(Extraline+Secondline[i]+Secondline[j]))-Mainline[i] is max
<==> Mainline[j]+Secondline[j]-(Mainline[i]-Secondline[i])-Dist+Extraline max
<==> -(Mainline[i]-Secondline[i]) max <==> (Mainline[i]-Secondline[i]) min (as everything else is fixed - Dist and Exline is given, we are considering a fixed j
<==> Diff[i] min. Normally we could just calculate Diff[i] normally, but constrain 1) gets in the way. We'll have to check whether the index i with min(Diff[i]) for 1...j-1 also
satisfies inequation 1 or not.
But, since that Diff[i] is already a minimum, if Sum[j]-Diff[i] is still <= Dist, there doesn't exist any smaller value of Diff[i], and thus this Sum[i]-Diff[i] is the smallest we'll
ever get => If it satisfies, cool, take it. Otherwise, there doesn't exist any i that could form a valid square with j, so just skip this j. In the meantime, update the minimum value
of Diff accordingly
*/
//Determining the prefix minimum of Diff[i] for all i, then proceed to create all Rightmost Topleft square possible
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);
}
}
//Phase 2: Creating all necessary Leftmost BottomRight squares
/*
Same as the Rightmost TopLeft squares, but this time those squares are the ones where the lines that overlaps with its BottomRight bounds (which, again, is in the form x-y=a) and a
as small as possible.
Constrain inequations:
1) Sum[j]-Diff[i]>Dist (so that the square is "valid")
2) Mainline[j]+(Dist-(Extraline+Secondline[i]+Secondline[j]))-Mainline[i] min
<==> (Mainline[j]-Secondline[j])-(Mainline[i]+Secondline[i])+Dist-Extraline min
<==> -(Mainline[i]+Secondline[i]) min (again, everything else is fixed)
<==> Sum[i] max
*/
/*
As the algorithm has to run only O(N) operations per binary search iteration, finding the min-max has to be done in linear time. We should try to find a way to keep the "current minimum
valid station" or some shit after constantly adding in new stations. From experience, you should be able to tell that we're going to have to use stacks or something combined with some
additional property to find the min/max value something something in linear time.
Notice that: As Sum[j] is increasing, we are getting new candidates for Diff[i], while the old valid indexes of i still satisfies the inequation (if Sum[j]-Diff[i]>Dist, then
Sum[j]+something that is positive-Diff[i] also has to be >Dist as well). As such, if we only iterate through a certain set of indexes j1,j2,....,jk such that Sum[j1]<Sum[j2]<...<Sum[jk],
we can keep track of the maximum value of Sum[i] for all valid i, as an already valid i would still be valid for the further Sum[j]s.
Right now, we're not really sure whether if this works or not, but let's just try to work with it for a minute or two, no?
For a station j, we'll call j a "Dominator" if the value of Sum[j] is the largest out of all values of Sum[a], for 1<=a<=j. (I am not making this up, this is literally what is used by the
official editorial.) Using the above property, if we only query through only dominators (instead of all stations), we can find the corresponding maximum valid value of Sum[i] in
linear time.
The problem is: Does this even work? Could we guarantee that the Leftmost BottomRight square will always be formed when we "combine" some i and j, such that i<j and j is a dominator?
Well, you could go ahead and try to implement it and proof by AC. (spoilers: it does). Here's why.
To proof that the Leftmost BottomRight square will always be the product of combining a dominator j with some valid i, we'll have to think very much backwards. This time, instead of fixing
the value of j, we will have to fix the value of i instead.
Let's look at our 2nd constrain inequation again: (Mainline[j]-Secondline[j])-(Mainline[i]+Secondline[i])+Dist-Extraline is min. As everything else is locked, we have:
(Mainline[j]-Secondline[j]) has to be min.
We now have:
Mainline[j] is max of all values of Mainline[k] for all 1<=k<=j => 2*Mainline[j] is max of all values of 2*Mainline[k] for all 1<=k<=j
Diff[j] is min of all values of Diff[k] for all 1<=k<=j
=> 2*Mainline[j]-(Mainline[j]-Secondline[j]) is max of 2*Mainline[k]-(Mainline[k]-Secondline[k]) for all 1<=k<=j
=> Mainline[j]+Secondline[j]=Sum[j] is max of Sum[k] for all 1<=k<=j
=> By definition, station j is a Dominator
=> If we can create a valid Leftmost BottomRight square by combining station i and some j>i, station j has to be a dominator
=> Checking only Dominators will still guarantee to find the Leftmost BottomRight square
*/
/*
As such, we can do the following to determine the Leftmost BottomRight square:
Step 1: Determining all Dominators.
Step 2: While transitioning from a Dominator to the next one, update the set of new valid candidates for i, and change the current maximum value of Sum[i] accordingly
Step 3: Now, create the Leftmost BottomRight square that could be created from this Dominator. Update the bounds accordingly. Move on to the next Dominator
Step 1 and 3 is literally trivial, but step 2 is quite a bit troublesome. Finding the largest value of Sum[i] that satisfies requires a little bit of extra work. Like, 30 lines of code
or something.
When moving from a dominator to the next, it's not guaranteed that all stations in between will be valid (see: Sample input 2: Moving from the 2nd dominator (at station 2) to the 3rd
dominator (at station 6), there aren't any squares formed by station 3 yet. It takes until we started considering the 4th dominator (at station 8) for any squares featuring station 3
to be formed
=> We'll have to determine the first dominator j that could make a valid square when combined with station i. All later dominators would be able to create squares with station i
(look at why we even started considering only dominators as the larger value in a pair of indexes that forms a square in the first place).
Now, we call station i "submissive and breedable" to station j if the following 2 conditions hold:
- i is dominated by j (or: i<j and station j is a dominator)
- Sum[j]-Diff[i]>Dist (so that it could "breed" a square)
As we're iterating through dominators (read: in order of increasing Sum[j], the maximum value for Diff[i] that could "breed" a square is constantly increasing. Which means, assuming
if we tempolarily ditch the 1st condition entirely, if we sort the indexes in order of increasing Diff[i], we can constantly update the set of "valid" indicies after moving into
a new dominator simply by moving the bound closer to the end of the sorted array
=>....Yeah, just sort everything (in a secondary array) and try to work with it and overcome the 1st condition
Now, scroll down for the sorting part
*/
k=1;
/*
EnterSquareMakingOrgy[i]: The set of indexes that is made submissive and breedable by the i-th dominator. When we get to the i-th dominator, we allow all of the indexes in this stack to
"get" into the "these indexes could make valid squares" set (or, quite literally, let them enter the "square making orgy") and then update the max value of valid Sum[i] accordingly.
This is (probably) not a joke.
*/
CurMaxsum=-lim;
int Pointer=1;
MaxSumIndex=1;
//BIG MISTAKE: DO NOT start from 1. Like, wtf is the first fucking station even going to dominate? (unless it is into selfcest. that is still not a thing in this task though
//So, yeah, start from the 2nd dominator. Don't waste an hour trying to debug (like I did) (actually only 5 minutes)
for(int i=2;i<Dominators.size();i++){
/*
Now, when will station i be both submissive AND breedable entirely to station j? When station i is dominated by station j, and station i is breedable by station j, of course
First dominator that makes i submissive: ID of the dominator assigned to station i = A.
First Dominator that makes i breedable: ID of the dominator we're considering right now = B. We say that i is primarily made breedable by the B-th dominator
First Dominator that makes i both submissive AND breedable: First station that satisfy both conditions aka max(A,B), lol
*/
while(Pointer<=n&&Sum[Dominators[i]]-Diff[SortedByDiff[Pointer].ID]>Dist){
//This is the list of all stations made breedable primarily by the i-th dominator
EnterSquareMakingOrgy[max(i,SortedByDiff[Pointer].NextDominatorID)].push(SortedByDiff[Pointer].ID);
Pointer++;
//cout<<Pointer<<" ";
}
//Allowing the stations made submissive and breedable by i-th dominator into the "valid" set/square making orgy. Updating the value of current max valid Sum
while(!EnterSquareMakingOrgy[i].empty()){
if(CurMaxsum<Sum[EnterSquareMakingOrgy[i].top()]){
CurMaxsum=Sum[EnterSquareMakingOrgy[i].top()];
MaxSumIndex=EnterSquareMakingOrgy[i].top();
}
EnterSquareMakingOrgy[i].pop();
}
//Make the corresponding Leftmost BottomRight square
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;
}
//Phase 3: Checking whether there is a pair of stations (i,j) that is valid (a "solution" to all inequations formed by the squares, in O(N)
/*
For every single point formed by considering a pair of station (i,j), we have: (Coordinate of that point)=(Mainline[j],Mainline[i])
For each point, there is an unique pair of lines Y=X-A and Y=X-B that goes through it (as, given the sum and difference of 2 numbers, we could find a single pair
of numbers that satisfies both equations)
Now, the conditions for a point (x,y) to be inside the intersection of all squares would be equal to:
BoundTopLeft <= X-Y <= BoundBottomRight
BoundBottomLeft <= X+Y <= BoundTopRight
Now, when we consider station i and j (with j>i),we can now modify the inequations to:
BoundTopLeft <= Mainline[j]-Mainline[i] <= BoundBottomRight
BoundBottomLeft<= Mainline[j]+Mainline[i] <= BoundTopRight
As we iterate through dominator j in increasing order, we notice that:
- The indexes of i that satisfies the first inequation will constantly move towards the end of the list of stations when j increases
- The indexes of i that satisfies the second inequation will constantly move towards the beginning of the list of stations as j increases
- If those 2 ranges intersects at at least 1 station for a certain i, we know for sure that this pair of stations of (j,the intersection) satisfies both inequations,
and is inside the "bound", and the answer is valid
=> Just use 4 pointers, 2 for managing the range of indexes that satisfy the 1st inequation, 2 for the 2nd inequation
*/
P1=1;
P2=n+1;
P3=1;
P4=n+1;
ok=0;
/*
While two-pointers are very simple, do not underestimate it (your skill issue, to be precise). My dumb ass spent 2 hour trying to iterate through only dominators as endpoint of the shortcut
and wondering why tf doesn't it work out, lol.
Reminder: Optimal squares are only created with dominators as endpoint, Shortcut can be between whatever.
ALso, you'll kinda have to "prepare" beforehand: Calculate where the bounds end up for i=1, then move the bounds accordingly. Otherwise, you'll waste
4 hours for something supposedly trivial like 2-pointers. Definitely funny.
......also remember what each bound stands for as well. Dumb fucker forgot that we are only considering pairs of stations (j,i) (with j>i) and not the
other way around, proceed to debug for 5 fucking hours not understanding why the code managed to fuck up so bad. To think that it still pass 50% of the
tests.......
(check the standard i/o version of this task on dmoj.ca to see the funny)
*/
//For the initialization (working with Mainline[1], it is 0, so I leave it out
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){
//Checking whether the 2 ranges intersects
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--;
}
//Can't create a station with either the 1st range or 2nd range not being valid, or if there is no valid range at all
//Example: if the change from Mainline[i] to Mainline[i+1] is too sudden, it is possible for the range [BoundTopLeft,BoundBottomRight] to be skipped over entirely, so there is station
//that could create a satisfying shortcut
if(P1<=P2&&P3<=P4){
//Checking whether the 2 ranges intersects
if(abs(max(P2,P4)-min(P1,P3))<=P2-P1+P4-P3){
ok=1;
return ok;
}
}
}
// cout<<"\n";
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;
//For utility later
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);
//Let Mainline Station 1 be the "root" of the network (yeah, it is a tree, how could you tell
//Distance between Secondline station i and Secondline station j = Mainline[i]-Mainline[j]+Secondline[i]+Secondline[j]
// = (Mainline[i]+Secondline[i])-(Mainline[j]-Secondline[j]).
//Thus, the greatest distance between Secondline station i and some Secondline station j before station i is with a station j with the smallest value of (Mainline[j]-Secondline[j]).
//The largest value of Dist(Secondline station i, Secondline station j) over all i is the tree diameter.
}
CurMindiff=min(CurMindiff,Diff[i]);
}
long long l=1,r=TreeDiameter;
//No reason to search for any answer larger than the diameter of the tree - if adding a segment makes the answer larger than just using the base network, why even bother
//Now, look at the explaination for the PossibleDiameter function first, before looking at this next sorting part.
/*
Okay, now we're back to the sorting part again.
By combining the 2 restrictions, it is obvious what we should care about in order to make station i submissive and breedable:
- The first dominator that dominates station i (the closest dominator to the right of station i)
- The index of station i itself - which would then be used to determine the value of Diff[i], and thus determine the first dominator that makes station i breedable
We only need to sort once though, as the only thing that matters is the order of values of Diff[i]. Other things might be different between different values of Dist, but this array
still works the same
*/
Dominators.clear();
Dominators.push_back(0);
//Determining Dominators, thus finding the ID of the immediate next dominator from station i (ex:ID=3 means the 3rd dominator is the first dominator to the right of station i
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);
for(int i=0;i<=Dominators.size()+3;i++){
EnterSquareMakingOrgy.push_back(TStack);
}
//Okay, now back to the top again
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
shortcut.cpp: In function 'long long int PossibleDiameter(long long int)':
shortcut.cpp:171:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for(int i=2;i<Dominators.size();i++){
| ~^~~~~~~~~~~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(long long int, std::vector<long long int>, std::vector<long long int>, long long int)':
shortcut.cpp:341:37: warning: narrowing conversion of 'Dominators.std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
341 | SortedByDiff[i]={i,Dominators.size()};
| ~~~~~~~~~~~~~~~^~
shortcut.cpp:344:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
344 | for(int i=0;i<=Dominators.size()+3;i++){
| ~^~~~~~~~~~~~~~~~~~~~~
shortcut.cpp:362:1: warning: control reaches end of non-void function [-Wreturn-type]
362 | }
| ^
/usr/bin/ld: /tmp/ccFX9l91.o: in function `main':
grader.cpp:(.text.startup+0x124): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
