Submission #1016898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016898		blue	Shortcut (IOI16_shortcut)	C++17	0 / 100	18 ms	32344 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
 
const int mxn = 1'000'000;
const ll INF = 10'000'000'000'000'000LL;
 
vll x(1+mxn);
vll y(1+mxn);
 
long long find_shortcut(int n, vector<int> l_, vector<int> d_, int c_)
{
    x[1] = 0;
    for(int i = 2; i <= n; i++) x[i] = x[i-1] + l_[i-2];
 
    for(int i = 1; i <= n; i++) y[i] = d_[i-1];
 
    ll l = c_; //shortcut length
 
 
    int* ord = new int[1+n];
    for(int i = 1; i <= n; i++) ord[i] = i;
 
    sort(ord+1, ord+n+1, [] (int u, int v)
    {
        return y[u] - x[u] > y[v] - x[v];
    });
 
// cerr << "\n\n\n";
    // for(int i = 1; i <= n; i++) cerr << i << " : " << x[i] << ' ' << y[i] << ' ' << y[i] - x[i] << '\n';
    //
    // cerr << "ord = ";
    // for(int oi = 1; oi <= n; oi++) cerr << ord[oi] << ' ';
    // cerr << '\n';
 
 
// cerr << "\n\n\n";
 
 
 
 
 
 
 
    pair<ll, int> xpy_max[1+n], xpy_max2[1+n];
    xpy_max[0] = xpy_max2[0] = {-INF, 0};
 
    // xpy_max[1] = {x[ord[1]] + y[ord[1]], ord[1]};
    // xpy_max2[1] = {-INF, 0};
 
    // cerr << "COMPUTING MAX\n";
 
    for(int i = 1; i <= n; i++)
    {
        xpy_max[i] = xpy_max[i-1];
        xpy_max2[i] = xpy_max2[i-1];
 
        pair<ll, int> nw = {x[ord[i]] + y[ord[i]], ord[i]};
 
        if(nw <= xpy_max2[i]) ;
        else if(nw <= xpy_max[i]) xpy_max2[i] = nw;
        else
        {
            xpy_max2[i] = xpy_max[i];
            xpy_max[i] = nw;
        }
 
        // cerr << "element = " << ord[i] << " : ";
        // cerr << xpy_max[i].first << "|" << xpy_max[i].second << " , " << xpy_max2[i].first << "|" << xpy_max2[i].second << '\n';
    }
 
 
 
    // cerr << "\n\n\n\n";
 
    // cerr << "COMPUTING MIN\n";
 
    pair<ll, int> xdy_min[1+n], xdy_min2[1+n];
    xdy_min[0] = xdy_min2[0] = {INF, 0};
 
    for(int i = 1; i <= n; i++)
    {
        xdy_min[i] = xdy_min[i-1];
        xdy_min2[i] = xdy_min2[i-1];
 
        pair<ll, int> nw = {x[ord[i]] - y[ord[i]], ord[i]};
 
        if(nw >= xdy_min2[i]);
        else if(nw >= xdy_min[i]) xdy_min2[i] = nw;
        else
        {
            xdy_min2[i] = xdy_min[i];
            xdy_min[i] = nw;
        }
 
        // cerr << "element = " << ord[i] << " : ";
        // cerr << xdy_min[i].first << "|" << xdy_min[i].second << " , " << xdy_min2[i].first << "|" << xdy_min2[i].second << '\n';
    }
 
 
    sort(ord+1, ord+n+1, [] (int u, int v)
    {
        return y[u] - x[u] > y[v] - x[v];
    });
 
    vi I(n);
    for(int i = 0; i < n; i++) I[i] = i+1;
    sort(I.begin(), I.end(), [] (int u, int v)
    {
        return x[u] + y[u] < x[v] + y[v];
    });
 
 
    ll lo = 1;
    // ll hi = (1'000'000'000'000'000'000LL);
    ll hi = 1'000'000'000LL * ll(n+2);
 
    while(lo != hi)
    {
        ll k = (lo+hi)/2;
 
        // cerr << "\n\n\n";
        // cerr << "k = " << k << '\n';
 
        ll sum_lo = -INF;
        ll sum_hi = INF;
 
        ll diff_lo = -INF;
        ll diff_hi = INF;
 
        int i_ind = 0;
 
        for(int q = 0; q < n; q++)
        {
            int j = I[q];
 
            while(i_ind + 1 <= n && y[ord[i_ind + 1]] - x[ord[i_ind + 1]] > k - (x[j] + y[j]))
            {
                int i = ord[i_ind+1];
                if(!(y[i] - x[i] > k - (x[j] + y[j]))) break;
                i_ind++;
                assert(i < j);
            }
 
            ll xpy_maxval = (xpy_max[i_ind].second != j ? xpy_max[i_ind].first : xpy_max2[i_ind].first);
            ll xdy_minval = (xdy_min[i_ind].second != j ? xdy_min[i_ind].first : xdy_min2[i_ind].first);
 
            sum_lo = max(sum_lo, xpy_maxval + x[j] + y[j] + l - k);
 
            sum_hi = min(sum_hi, xdy_minval + x[j] - y[j] + k - l);
 
            diff_hi = min(diff_hi, -(xpy_maxval) + x[j] - y[j] + k - l);
 
            diff_lo = max(diff_lo, -(xdy_minval) + x[j] + y[j] + l - k);
        }
 
        // cerr << sum_lo << ' ' << sum_hi << ' ' << diff_lo << ' ' << diff_hi << '\n';
 
        bool works = 0;
 
        for(int i = 1; i <= n; i++)
        {
            for(int j = i+1; j <= n; j++)
            {
                if(sum_lo <= x[i] + x[j] && x[i] + x[j] <= sum_hi)
                {
                    if(diff_lo <= x[j] - x[i] && x[j] - x[i] <= diff_hi)
                    {
                        works = 1;
                    }
                }
                // cerr << "val = " << x[i] + x[j] << ' ' << x[j] - x[i] << '\n';
            }
        }
        // cerr << "works = " << works << '\n';
 
        // cerr << lo << ' ' << hi << " -> ";
 
        if(works) hi = k;
        else lo = k+1;
 
        // cerr << lo << ' ' << hi << '\n';
    }
 
 
    return lo;
}

• 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