Submission #502675

#	Time	Username	Problem	Language	Result	Execution time	Memory
502675		blue	Shortcut (IOI16_shortcut)	C++17	100 / 100	1873 ms	95288 KiB

shortcut

#include "shortcut.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

const int mxn = 1'000'000;
const ll INF = 1'000'000'000'000'000'000LL;

vll x(1+mxn);
vll y(1+mxn);

vll xpy(1+mxn);
vll xdy(1+mxn);
vll ydx(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


        for(int i = 1; i <= n; i++)
        {
            xpy[i] = x[i] + y[i];
            xdy[i] = x[i] - y[i];
            ydx[i] = -xdy[i];
        }


    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 ydx[u] > ydx[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 = {xpy[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+3], xdy_min2[1+3];
    xdy_min[0] = xdy_min2[0] = {INF, 0};

    for(int i = 1; i <= 2; i++)
    {
        xdy_min[i] = xdy_min[i-1];
        xdy_min2[i] = xdy_min2[i-1];

        pair<ll, int> nw = {xdy[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 xpy[u] < xpy[v];
    });


    ll lo = 1;
    // ll hi = (1'000'000'000'000'000'000LL);
    ll hi = 2'000'000'000LL + x[n] - x[1];


    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 && ydx[ord[i_ind+1]] > k - xpy[j])
            {
                int i = ord[i_ind+1];
                if(!(-xdy[i] > k - xpy[j])) break;
                i_ind++;
            }

            ll xpy_maxval = (xpy_max[i_ind].second != j ? xpy_max[i_ind].first : xpy_max2[i_ind].first);

            int d_ind = min(i_ind, 2);
            ll xdy_minval = (xdy_min[d_ind].second != j ? xdy_min[d_ind].first : xdy_min2[d_ind].first);


            sum_lo = max(sum_lo, xpy_maxval + xpy[j]);

            diff_hi = min(diff_hi, xdy[j] - xpy_maxval);

            sum_hi = min(sum_hi, xdy_minval + xdy[j]);

            diff_lo = max(diff_lo, xpy[j] - xdy_minval);
        }

        sum_lo += l-k;
        diff_hi += k-l;
        sum_hi += k-l;
        diff_lo += 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';

        int b = 1;

        for(int a = 1; a <= n; a++)
        {
            ll ctr = max(sum_lo - x[a], diff_lo + x[a]);
            while(b > 1 && x[b-1] >= ctr) b--;
            while(b <= n && x[b] < ctr) b++;

            if(1 <= b && b <= n)
                if(sum_lo <= x[a] + x[b])
                    if(x[a] + x[b] <= sum_hi)
                        if(diff_lo <= x[b] - x[a])
                            if(x[b] - x[a] <= diff_hi)
                                works = 1;
        }





        // cerr << lo << ' ' << hi << " -> ";

        if(works) hi = k;
        else lo = k+1;

        // cerr << lo << ' ' << hi << '\n';
    }


    return lo;
}

• 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