Submission #791685

#	Time	Username	Problem	Language	Result	Execution time	Memory
791685		alvingogo	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	304 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=2e18;
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;
    int flag=0;
    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++;
            flag=1;
        }
        if(flag){
            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=-1,r1=n,l2=-1,r2=n;
    for(int i=0;i<n;i++){
        while(l1+1<=i && v[l1+1]<=a2-v[i]){
            l1++;
        }
        while(l2+1<=i && v[l2+1]<=a4+v[i]){
            l2++;
        }
        while(r1-1>=0 && v[r1-1]>=a1-v[i]){
            r1--;
        }
        while(r2-1>=0 && v[r2-1]>=a3+v[i]){
            r2--;
        }
        int b=min(l1,l2),c=max(r1,r2);
        if(b>=c){
            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:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         while(l<dq.size() && q[dq[l]]+p[i]>D){
      |               ~^~~~~~~~~~
shortcut.cpp:37:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         while(dq.size()>l && q[dq.back()]<=q[i]){
      |               ~~~~~~~~~^~

• 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