oj.uz

Submission #1011283

# Submission time Handle Problem Language Result Execution time Memory
1011283 2024-06-30T08:59:27 Z bachhoangxuan Shortcut (IOI16_shortcut) C++17
0 / 100
 2000 ms 600 KB 
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;

ll find_shortcut(int n, std::vector<int> _x, std::vector<int> _d, int c)
{
    vector<ll> x(n),d(n);
    for(int i=0;i<n;i++) x[i]=(i?x[i-1]+_x[i-1]:0),d[i]=_d[i];
    auto check = [&](ll S){
        deque<int> dq;
        ll a0=-inf,a1=inf,b0=-inf,b1=inf,m0=-inf,m1=-inf,cS=S-c;
        for(int i=0;i<n;i++){
            if(m0+d[i]+x[i]>S){
                while(!dq.empty() && d[dq.front()]-x[dq.front()]+d[i]+x[i]>S){
                    int t=dq.front();dq.pop_front();
                    m1=max(m1,d[t]+x[t]);
                }
                a0=max(a0,d[i]+x[i]+m1-cS);
                a1=min(a1,cS-d[i]+x[i]-m0);
                b0=max(b0,d[i]-x[i]+m1-cS);
                b1=min(b1,cS-d[i]-x[i]-m0);
            }
            m0=max(m0,d[i]-x[i]);
            while(!dq.empty() && d[dq.back()]-x[dq.back()]<=d[i]-x[i]) dq.pop_back();
            dq.push_back(i);
        }
        //cout << a0 << ' ' << a1 << ' ' << b0 << ' ' << b1 << '\n';
        int la=0,lb=n,ra=-1,rb=n-1;
        for(int i=n-1;i>=0;i--){
            while(la<n && x[i]+x[la]<a0) la++;
            while(ra<n-1 && x[i]+x[ra+1]<=a1) ra++;
            while(lb>0 && x[i]-x[lb-1]<=b1) lb--;
            while(rb>=0 && x[i]-x[rb]<b0) rb--;
            int L=max({la,lb,i}),R=min(ra,rb);
            //cout << la << ' ' << lb << ' ' << ra << ' ' << rb << '\n';
            if(L<=R) return true;
        }
        return false;
    };
    ll l=0,r=1e16,res=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB n = 4, 80 is a correct answer
2 Correct 0 ms 600 KB n = 9, 110 is a correct answer
3 Correct 0 ms 348 KB n = 4, 21 is a correct answer
4 Correct 0 ms 348 KB n = 3, 4 is a correct answer
5 Correct 0 ms 348 KB n = 2, 62 is a correct answer
6 Correct 0 ms 348 KB n = 2, 3 is a correct answer
7 Correct 1 ms 348 KB n = 3, 29 is a correct answer
8 Correct 0 ms 348 KB n = 2, 3 is a correct answer
9 Correct 0 ms 348 KB n = 2, 3 is a correct answer
10 Execution timed out 2036 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -