Submission #1023333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023333		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];

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++){
    //         sum[0][0]=max()
    //     }
    // }
    {
        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;
    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=inf,res=0;
    // cout<<check(80)<<"\n";
    // return 51;
    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:105:40: warning: left operand of comma operator has no effect [-Wunused-value]
  105 |             if(r>=0)sum[1][0]=(sum[1][0],-a[i].S+b[r].S+c-L);
      |                                ~~~~~~~~^
shortcut.cpp:109:9: warning: unused variable 'r' [-Wunused-variable]
  109 |     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