Submission #289540

#	Time	Username	Problem	Language	Result	Execution time	Memory
289540		Kastanda	Shortcut (IOI16_shortcut)	C++11	93 / 100	2076 ms	20264 KiB

shortcut

// M
#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const int N = 300005;
int n, cost, P[N], Rev[N], Target[N];
ll X[N], L[N], D[N];
ll F[2][N];
inline void Add(int w, int i, ll val)
{
        for (; i < N; i += i & - i)
                F[w][i] = max(F[w][i], val);
}
inline ll GetMax(int w, int i)
{
        ll Mx = -1e18;
        for (; i; i -= i & - i)
                Mx = max(Mx, F[w][i]);
        return Mx;
}
inline bool Solve(ll md)
{
        memset(F, -63, sizeof(F));
        for (int i = 1; i <= n; i ++)
        {
                int le = 0, ri = n + 1, mid;
                while (ri - le > 1)
                {
                        mid = (le + ri) >> 1;
                        if (D[P[mid]] - X[P[mid]] + D[i] + X[i] > md)
                                le = mid;
                        else
                                ri = mid;
                }
                Target[i] = le;
        }

        ll le_sm = -1e18, ri_sm = 1e18;
        ll le_mn = -1e18, ri_mn = 1e18;
        for (int j = 1; j <= n; j ++)
        {
                // Optimizing all the nonsense from below :
                // Let's break it down :
                // 1. X[i]-a + X[j]-b <= value          ==>             a + b >= (X[i] + D[i]) + (X[j] + D[j]) - (md - cost)
                // 2. X[i]-a + b-X[j] <= value          ==>             b - a <= (md - cost) + (X[j] - D[j]) - (X[i] + D[i])
                // 3. a-X[i] + X[j]-b <= value          ==>             b - a >= (X[j] + D[j]) - (X[i] - D[i]) - (md - cost)
                // 4. a-X[i] + b-X[j] <= value          ==>             b + a <= (md - cost) + (X[i] - D[i]) + (X[j] - D[j])

                le_sm = max(le_sm, X[j] + D[j] - (md - cost) + GetMax(0, Target[j]));
                ri_sm = min(ri_sm, (md - cost) + (X[j] - D[j]) - GetMax(1, Target[j]));

                le_mn = max(le_mn, X[j] + D[j] - (md - cost) + GetMax(1, Target[j]));
                ri_mn = min(ri_mn, (md - cost) + (X[j] - D[j]) - GetMax(0, Target[j]));


                Add(0, Rev[j], X[j] + D[j]),
                Add(1, Rev[j], D[j] - X[j]);

                /* This is gibberish now.

                // Requiring a bridge of form (a, b) where
                // D[i] + D[j] + |X[i]-a| + |X[j]-b| + cost <= md
                // |X[i]-a| + |X[j]-b| <= md - cost - D[i] - D[j]

                ll value = md - cost - D[i] - D[j];
                // Let's break it down :
                // 1. X[i]-a + X[j]-b <= value          ==>             a + b >= X[i] + X[j] - value
                // 2. X[i]-a + b-X[j] <= value          ==>             b - a <= value + X[j] - X[i]
                // 3. a-X[i] + X[j]-b <= value          ==>             b - a >= X[j] - X[i] - value
                // 4. a-X[i] + b-X[j] <= value          ==>             b + a <= value + X[i] + X[j]

                le_sm = max(le_sm, X[i] + X[j] - value); // 1.
                ri_sm = min(ri_sm, value + X[i] + X[j]); // 4.

                le_mn = max(le_mn, X[j] - X[i] - value); // 3.
                ri_mn = min(ri_mn, value + X[j] - X[i]); // 2.

                */
        }

        for (int j = 1; j <= n; j ++)
        {
                // le_sm <= X[j] + X[i]         ==>     le_sm - X[j] <= X[i]
                // ri_sm >= X[j] + X[i]         ==>     ri_sm - X[j] >= X[i]
                // le_mn <= X[j] - X[i]         ==>     X[j] - le_mn >= X[i]
                // ri_mn >= X[j] - X[i]         ==>     X[j] - ri_mn <= X[i]

                ll le_val = max(le_sm - X[j], X[j] - ri_mn);
                ll ri_val = min(ri_sm - X[j], X[j] - le_mn);

                int i = lower_bound(X + 1, X + j + 1, le_val) - X;
                if (i <= j && X[i] >= le_val && X[i] <= ri_val)
                        return 1;
        }
/*
        for (int i = 1; i <= n; i ++)
                for (int j = i; j <= n; j ++)
                        if (X[i] + X[j] >= le_sm && X[i] + X[j] <= ri_sm && X[j] - X[i] >= le_mn && X[j] - X[i] <= ri_mn)
                                return 1;*/
        return 0;
}
long long find_shortcut(int _n, vector < int > _L, vector < int > _D, int _cost)
{
        n = _n;
        cost = _cost;
        for (int i = 1; i < n; i ++)
                L[i] = _L[i - 1];
        for (int i = 1; i <= n; i ++)
                D[i] = _D[i - 1];

        for (int i = 2; i <= n; i ++)
                X[i] = X[i - 1] + L[i - 1];

        for (int i = 1; i <= n; i ++)
                P[i] = i;
        sort(P + 1, P + n + 1, [&](int i, int j){return make_pair(D[i] - X[i], i) > make_pair(D[j] - X[j], j);});
        for (int i = 1; i <= n; i ++)
                Rev[P[i]] = i;

        ll le = 0, ri = 7e15, md;
        while (ri - le > 1)
        {
                md = (le + ri) >> 1;
                if (Solve(md))
                        ri = md;
                else
                        le = md;
        }
        return ri;
}

• 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: 0 / 4
• Subtask 8: 0 / 3