oj.uz

Submission #902546

# Submission time Handle Problem Language Result Execution time Memory
902546 2024-01-10T16:17:51 Z abcvuitunggio Shortcut (IOI16_shortcut) C++17
0 / 100
 0 ms 348 KB 
#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];
    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 <int, 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(x,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,s[i]+d[i]+c-mid+x);
            mxx=min(mxx,s[i]-d[i]-c+mid+y);
            mny=max(mny,s[i]+d[i]+c-mid-y);
            mxy=min(mxy,s[i]-d[i]-c+mid-x);
        }
        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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB n = 4, incorrect answer: jury 80 vs contestant 90
2 Halted 0 ms 0 KB -