Submission #902551

#	Time	Username	Problem	Language	Result	Execution time	Memory
902551		abcvuitunggio	Shortcut (IOI16_shortcut)	C++17	100 / 100	1031 ms	61836 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<51;
const int mxn=1000001;
long long s[mxn];
long long find_shortcut(int n, vector <int> l, vector <int> d, int c){
    for (int i=1;i<n;i++)
        s[i]=s[i-1]+l[i-1];
    s[n]=INF;
    long long lo=0,hi=INF,kq=-1;
    while (lo<=hi){
        long long mid=(lo+hi)>>1,mnx=-INF,mxx=INF,mny=-INF,mxy=INF,x=-INF,y=INF;
        deque <pair <long long, int>> q;
        for (int i=0;i<n;i++){
            while (!q.empty()&&s[i]+d[i]-q.front().first>mid){
                int i=q.front().second;
                x=max(x,s[i]+d[i]);
                y=min(y,s[i]-d[i]);
                q.pop_front();
            }
            while (!q.empty()&&q.back().first>=s[i]-d[i])
                q.pop_back();
            q.push_back({s[i]-d[i],i});
            mnx=max(mnx,x+c-mid+s[i]+d[i]);
            mxx=min(mxx,y-c+mid+s[i]-d[i]);
            mny=max(mny,x+c-mid-s[i]+d[i]);
            mxy=min(mxy,y-c+mid-s[i]-d[i]);
        }
        int tmp=0,j=n,ch=0;
        for (int i=0;i<n;i++){
            long long l=max(mnx-s[i],s[i]-mxy);
            if (mnx-s[i]<s[i]-mxy&&!tmp){
                j=0;
                tmp=1;
            }
            if (tmp)
                while (j<n&&s[j]<l)
                    j++;
            else{
                while (j>=0&&s[j]>=l)
                    j--;
                j++;
            }
            if (j<n&&s[j]<=min(mxx-s[i],s[i]-mny)){
                ch=1;
                break;
            }
        }
        if (ch){
            kq=mid;
            hi=mid-1;
        }
        else
            lo=mid+1;
    }
    return kq;
}

• 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