| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1075073 | amirhoseinfar1385 | Shortcut (IOI16_shortcut) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=17,kaf=(1<<lg);
long long inf=1e16,n,c,inf2=2e9+5;
long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2;
struct segmentmn{
int seg[(1<<(lg+1))];
segmentmn(){
for(int i=0;i<kaf*2;i++){
seg[i]=inf2;
}
}
void clear(){
for(int i=0;i<kaf*2;i++){
seg[i]=inf2;
}
}
void upd(int i,int w){
i+=kaf;
seg[i]=w;
i>>=1;
while(i>0){
seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return inf2;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}segmn;
struct segmentmx{
int seg[(1<<(lg+1))];
segmentmx(){
for(int i=0;i<kaf*2;i++){
seg[i]=-inf2;
}
}
void clear(){
for(int i=0;i<kaf*2;i++){
seg[i]=-inf2;
}
}
void upd(int i,int w){
i+=kaf;
seg[i]=w;
i>>=1;
while(i>0){
seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
int pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return -inf;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}segmx;
void addr(long long x1,long long y1,long long x2,long long y2){
long long fx=x1+y1;
long long fy=x1-y1;
x1=fx;
y1=fy;
fx=x2+y2;
fy=x2-y2;
x2=fx;
y2=fy;
l1=max(l1,x1);
l2=min(l2,x2);
r1=max(r1,y2);
r2=min(r2,y1);
}
bool dakh(long long x,long long y){
long long fx=x+y;
long long fy=x-y;
x=fx;
y=fy;
if(x>=l1&&x<=l2&&y>=r1&&y<=r2){
return 1;
}
return 0;
}
bool check(long long mid){
l1=r1=-inf;
l2=r2=inf;
segmx.clear();
segmn.clear();
vector<pair<long long,long long>>allv;
int av=n+1;
for(int i=1;i<=n;i++){
allv.push_back(make_pair(-ps[i]+alld[i],-i));
allv.push_back(make_pair(mid-ps[i]-alld[i],i));
}
sort(allv.begin(),allv.end());
while((int)allv.size()>0){
auto x=allv.back();
allv.pop_back();
if(x.second<0){
segmx.upd(-x.second,alld[-x.second]+ps[-x.second]);
segmn.upd(-x.second,-alld[-x.second]+ps[-x.second]);
av=min(av,-x.second);
}
else{
if(av<x.second)
addr(ps[x.second],-mid+c+alld[x.second]+segmx.pors(1,0,kaf-1,0,x.second-1),ps[x.second],mid-c-alld[x.second]+segmn.pors(1,0,kaf-1,0,x.second-1));
}
}
vector<long long>vl;
for(long long i=1;i<=n;i++){
vl.push_back(ps[i]);
long long l=0,r=ps[n];
l=max(l,l1-ps[i]);
r=min(r,l2-ps[i]);
l=max(l,-r2+ps[i]);
r=min(r,-r1+ps[i]);
if(r>=l){
if(vl.back()>=l){
int p=lower_bound(vl.begin(),vl.end(),l)-vl.begin();
if(vl[p]<=r){
return 1;
}
}
}
}
return 0;
}
long long find_shortcut(int n_, std::vector<int> l, std::vector<int> d,int c_)
{
n=n_;
c=c_;
alld[1]=d[0];
for(long long i=2;i<=n;i++){
all[i]=l[i-2];
ps[i]=all[i]+ps[i-1];
alld[i]=d[i-1];
}
long long low=-1,high=inf,mid;
while(high-low>1){
mid=(high+low)>>1;
if(check(mid)){
high=mid;
}else{
low=mid;
}
}
return high;
}