Submission #1075014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075014		amirhoseinfar1385	Shortcut (IOI16_shortcut)	C++17	71 / 100	2071 ms	7772 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1000000+10;
long long inf=1e16,n,c;
long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2;
 
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;
    for(long long j=1;j<=n;j++){
        for(long long i=j+1;i<=n;i++){
            if(ps[i]-ps[j]+alld[i]+alld[j]>mid){
                addr(ps[i],-mid+c+alld[i]+alld[j]+ps[j],ps[i],mid-c-alld[i]-alld[j]+ps[j]);
            }
        }
    }
    set<long long>st;
    for(long long i=1;i<=n;i++){
        st.insert(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((*st.rbegin())>=l){
                auto x=st.lower_bound(l);
                if(*x<=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;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3