Submission #1075052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075052		amirhoseinfar1385	Shortcut (IOI16_shortcut)	C++17	71 / 100	2037 ms	49412 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1000000+10,lg=20,kaf=(1<<lg);
long long inf=1e16,n,c;
long long all[maxn],alld[maxn],ps[maxn],l1,l2,r1,r2;

struct segmentmn{
    long long seg[(1<<(lg+1))];
    segmentmn(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=inf;
        }
    }
    void clear(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=inf;
        }
    }
    void upd(int i,long long w){
        i+=kaf;
        seg[i]=w;
        i>>=1;
        while(i>0){
            seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
            i>>=1;
        }
    }
    long long 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 min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
    }
}segmn;
 
struct segmentmx{
    long long seg[(1<<(lg+1))];
    segmentmx(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=-inf;
        }
    }
    void clear(){
        for(int i=0;i<kaf*2;i++){
            seg[i]=-inf;
        }
    }
    void upd(int i,long long w){
        i+=kaf;
        seg[i]=w;
        i>>=1;
        while(i>0){
            seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
            i>>=1;
        }
    }
    long long 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;
    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]);
        }
        else{
            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));
        }
    }
/*    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