Submission #289489

#	Time	Username	Problem	Language	Result	Execution time	Memory
289489		Kastanda	Shortcut (IOI16_shortcut)	C++11	71 / 100	2083 ms	2628 KiB

shortcut

// M
#include<bits/stdc++.h>
#include "shortcut.h"
using namespace std;
typedef long long ll;
const int N = 1000006;
int n, cost, Nxt[N];
ll X[N], L[N], D[N];
inline bool Solve(ll md)
{
        /*for (int i = 1; i <= n; i ++)
        {
                // Nxt[i] is the smallest index such that : D[i] + D[Nxt[i]] + X[Nxt[i]] - X[i] > md
                // So we want the smallest index j that D[j] + X[j] > md - D[i] + X[i]
                Nxt[i] = GetFirst(i + 1, md - D[i] + X[i]);
        }

        // I should probably build a segment tree somewhere around here ...

        for (int l = 1; l <= n; l ++)
        {
                // Maximum possible value of i is minimum value of Nxt in [l, Nxt[l])
                int i = GetMin(l, Nxt[l]);
                i = min(i, GetFirst(l + 1, md - PreD[l] + X[l]));



                // Now let's find the maximum possible value for r
                // We should have D
        }*/

        ll le_sm = -1e18, ri_sm = 1e18;
        ll le_mn = -1e18, ri_mn = 1e18;
        for (int i = 1; i <= n; i ++)
                for (int j = i + 1; j <= n; j ++)
                        if (D[i] + D[j] + X[j] - X[i] > md)
                        {
                                // 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 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];

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