Submission #1023338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023338		vjudge1	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	348 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

#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))

using namespace std;

const int MAX=2e5+10;
const ll inf=1e18;

int n,c;
ll p[MAX];
pair<ll,ll> a[MAX],b[MAX];
ll add[MAX];
vector<int> d;

bool check(ll L){
    ll sum[2][2]={{-inf,inf},{-inf,inf}};
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[j]-p[i]+d[i]+d[j]+c<=L)continue;
            sum[0][0]=max(sum[0][0],p[i]+p[j]+d[i]+d[j]-L+c);
            sum[1][1]=min(sum[1][1],p[i]-d[i]+p[j]-d[j]+L-c);
            sum[1][0]=max(sum[1][0],p[j]+d[j]-p[i]+d[i]-L+c);
            sum[0][1]=min(sum[0][1],p[j]-d[j]-p[i]-d[i]+L-c);
        }
    }
    // {
    //     int r=-1;
    //     ll mx=-inf;
    //     for(int i=0;i<n;i++)add[i]=-inf;
    //     for(int i=0;i<n;i++){
    //         mx=max(mx,add[i]);
    //         while(r+1<n&&b[r+1].F<a[i].F-L){
    //             if(b[r+1].S<i){
    //                 mx=max(mx,a[b[r+1].S].F);
    //             }
    //             else{
    //                 add[b[r+1].S+1]=a[b[r+1].S].F;
    //             }
    //             r++;
    //         }
    //         if(mx!=-inf){
    //             assert(r<n);
    //             sum[0][0]=max(sum[0][0],mx+a[i].F+c-L);
    //         }
    //     }
    // }
    // {
    //     int r=-1;
    //     ll mn=inf;
    //     for(int i=0;i<n;i++)add[i]=inf;
    //     for(int i=0;i<n;i++){
    //         mn=min(mn,add[i]);
    //         while(r+1<n&&b[r+1].F<a[i].F-L){
    //             if(b[r+1].S<i){
    //                 mn=min(mn,-b[r+1].F);
    //             }
    //             else{
    //                 add[b[r+1].S+1]=-b[r+1].F;
    //             }
    //             r++;
    //         }
    //         if(r>=0)sum[0][1]=min(sum[0][1],L-c-a[i].F+mn);
    //     }       
    // }
    // {
    //     int r=-1;
    //     ll mn=inf;
    //     for(int i=0;i<n;i++)add[i]=inf;
    //     for(int i=0;i<n;i++){
    //         mn=min(mn,add[i]);
    //         while(r+1<n&&b[r+1].F<a[i].F-L){
    //             if(b[r+1].S<i){
    //                 mn=min(mn,b[r+1].F);
    //             }
    //             else{
    //                 add[b[r+1].S+1]=b[r+1].F;
    //             }
    //             r++;
    //         }
    //         if(r>=0){
    //             sum[1][1]=min(sum[1][1],mn+a[i].S+L-c);
    //         }
    //     }
    // }
    // {
    //     int r=-1;
    //     ll mx=-inf;
    //     for(int i=0;i<n;i++)add[i]=-inf;
    //     for(int i=0;i<n;i++){
    //         while(r+1<n&&b[r+1].F<a[i].F-L){
    //             if(b[r+1].S<i){
    //                 mx=max(mx,a[b[r+1].S].F);
    //             }
    //             else{
    //                 add[b[r+1].S+1]=a[b[r+1].S].F;
    //             }
    //             r++;
    //         }
    //         if(r>=0)sum[1][0]=(sum[1][0],-a[i].S+b[r].S+c-L);
    //     }
    // }
    // cout<<sum[0][0]<<" "<<sum[1][1]<<" "<<sum[1][0]<<" "<<sum[0][1]<<"\n";
    int r=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(sum[0][0]<=p[i]+p[j]&&p[i]+p[j]<=sum[1][1]&&sum[1][0]<=p[j]-p[i]&&p[j]-p[i]<=sum[0][1])return 1;
        }
        // while(r+1<i&&!(max(sum[1][1]+p[i],sum[0][0]-p[i])<=p[r]&&p[r]<=min(sum[1][0]-p[i],sum[0][1]+p[i])))r++;
        // if(r>=0&&max(sum[1][1]+p[i],sum[0][0]-p[i])<=p[r]&&p[r]<=min(sum[1][0]-p[i],sum[0][1]+p[i])){
        //     return 1;
        // }
    }
    return 0;
}

long long find_shortcut(int N, vector<int> G, vector<int> D, int C){
    n=N;
    c=C;
    d=D;
    for(int i=1;i<n;i++)p[i]=p[i-1]+G[i-1];
    for(int i=0;i<n;i++){
        // cout<<p[i]+d[i]<<"\n";
        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);
    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;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool check(long long int)':
shortcut.cpp:114:9: warning: unused variable 'r' [-Wunused-variable]
  114 |     int r=-1;
      |         ^

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