Submission #791767

#	Time	Username	Problem	Language	Result	Execution time	Memory
791767		alvingogo	Shortcut (IOI16_shortcut)	C++14	100 / 100	1332 ms	76948 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

typedef long long ll;
int n;
vector<int> l,d;
int c;
vector<ll> v,p,q;
const ll inf=1e18;
bool check(ll D){
    ll a1=-inf,a2=inf,a3=-inf,a4=inf;
    // a1,a2 => X+Y, a1,a3 => O > X
    vector<int> dq;
    int l=0,a=0;
    ll mp=-inf,mq=-inf;
    for(int i=0;i<n;i++){
        while(l<dq.size() && q[dq[l]]+p[i]>D){
            for(;a<=dq[l];a++){
                mp=max(mp,p[a]);
                mq=max(mq,q[a]);    
            }
            l++;
        }
        a1=max(a1,mp+p[i]+c-D);
        a2=min(a2,-mq-q[i]+D-c);
        a3=max(a3,mp+q[i]+c-D);
        a4=min(a4,-mq-p[i]+D-c);
        while(dq.size()>l && q[dq.back()]<=q[i]){
            dq.pop_back();
        }
        dq.push_back(i);
    }
    if(a1>a2 || a3>a4){
        return 0;
    }
    int l1=n-1,r1=n,l2=-1,r2=0;
    for(int i=0;i<n;i++){
        while(l1>=0 && v[l1]>a2-v[i]){
            l1--;
        }
        while(l2+1<n && v[l2+1]<=a4+v[i]){
            l2++;
        }
        while(r1-1>=0 && v[r1-1]>=a1-v[i]){
            r1--;
        }
        while(r2<n && v[r2]<a3+v[i]){
            r2++;
        }
        int b=min(l1,l2),w=max(r1,r2);
        if(b>=w && w<=i){
            return 1;
        }
    }   
    return 0;
}

ll find_shortcut(int N, vector<int> L, vector<int> D, int C)
{
    n=N;
    l=L;
    d=D;
    c=C;
    v.resize(n);
    p.resize(n);
    q.resize(n);
    for(int i=0;i<n;i++){
        if(i){
            v[i]=l[i-1];
            v[i]+=v[i-1];
        }
        p[i]=v[i]+d[i];
        q[i]=d[i]-v[i];
    }
    ll le=0,r=inf;
    while(r>le){
        ll m=(le+r)/2;
        if(check(m)){
            r=m;
        }
        else{
            le=m+1;
        }
    }
    return le;
}

Compilation message (stderr)

shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while(l<dq.size() && q[dq[l]]+p[i]>D){
      |               ~^~~~~~~~~~
shortcut.cpp:33:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |         while(dq.size()>l && q[dq.back()]<=q[i]){
      |               ~~~~~~~~~^~

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