#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
// #define int ll
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int MAX=1e6+10;
const ll inf=1e18;
int n,c;
vector<ll> p;
pair<ll,ll> a[MAX],b[MAX];
vector<int> d;
bool check(ll L){
ll sum[2][2]={{-inf,inf},{-inf,inf}};
{
int r=-1;
pair<ll,ll> mx={-inf,-inf},mx1={-inf,-inf};
for(int i=0;i<n;i++){
while(r+1<n&&b[r+1].F<a[i].F-L){
pair<ll,ll> bf={a[b[r+1].S].F,b[r+1].S};
if(mx<bf){
mx1=mx;
mx=bf;
}
else if(mx1<bf){
mx1=bf;
}
r++;
}
if(i!=mx.S)sum[0][0]=max(sum[0][0],mx.F+a[i].F+c-L);
else sum[0][0]=max(sum[0][0],mx1.F+a[i].F+c-L);
}
}
{
int r=-1;
pair<ll,ll> mn={inf,inf},mn1={inf,inf};
for(int i=0;i<n;i++){
while(r+1<n&&b[r+1].F<a[i].F-L){
pair<ll,ll> bf={-a[b[r+1].S].F,b[r+1].S};
if(mn>bf){
mn1=mn;
mn=bf;
}
else if(mn1>bf){
mn1=bf;
}
r++;
}
if(i!=mn.S)sum[0][1]=min(sum[0][1],L-c+a[i].S+mn.F);
else sum[0][1]=min(sum[0][1],L-c+a[i].S+mn1.F);
}
}
{
int r=-1;
pair<ll,ll> mn={inf,inf},mn1={inf,inf};
for(int i=0;i<n;i++){
while(r+1<n&&b[r+1].F<a[i].F-L){
pair<ll,ll> bf={b[r+1]};
if(bf<mn){
mn1=mn;
mn=bf;
}
else if(bf<mn1){
mn1=bf;
}
r++;
}
if(mn.S!=i)sum[1][1]=min(sum[1][1],mn.F+a[i].S+L-c);
if(mn1.S!=i)sum[1][1]=min(sum[1][1],mn1.F+a[i].S+L-c);
}
}
{
int r=-1;
pair<ll,ll> mx={-inf,-inf},mx1={-inf,-inf};
for(int i=0;i<n;i++){
while(r+1<n&&b[r+1].F<a[i].F-L){
pair<ll,ll> bf={-b[r+1].F,b[r+1].S};
if(bf>mx){
mx1=mx;
mx=bf;
}
else if(bf>mx1){
mx1=bf;
}
r++;
}
if(i!=mx.S)sum[1][0]=max(sum[1][0],a[i].F+mx.F+c-L);
else sum[1][0]=max(sum[1][0],a[i].F+mx1.F+c-L);
}
}
int B=-1;
for(int i=0;i<n;i++){
ll l=max(sum[0][0]-p[i],p[i]-sum[0][1]),r=min(sum[1][1]-p[i],p[i]-sum[1][0]);
if(l>r)break;
if(i==0){
B=lb(all(p),l)-p.begin();
}
while(B==-1||(B<sz(p)&&p[B]<l))B++;
while(B==sz(p)||(B>=0&&p[B]>r))B--;
if(B>=0&&B<sz(p)&&l<=p[B]&&p[B]<=r)return 1;
}
return 0;
}
long long find_shortcut(int N, vector<int> G, vector<int> D, int C){
n=N;
c=C;
d=D;
p.pb(0);
for(int i=1;i<n;i++)p.pb(p.back()+G[i-1]);
for(int i=0;i<n;i++){
a[i]={p[i]+d[i],p[i]-d[i]};
}
sort(a,a+n);
for(int i=0;i<n;i++){
b[i]={a[i].S,i};
}
sort(b,b+n);
// check(110);
// return 110;
ll l=0,r=a[n-1].F-b[0].F-1,res=a[n-1].F-b[0].F;
while(l<=r){
ll m=(l+r)/2;
if(check(m)){
r=m-1;
res=m;
}
else{
l=m+1;
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
