Submission #45218

#	Time	Username	Problem	Language	Result	Execution time	Memory
45218		reality	Shortcut (IOI16_shortcut)	C++17	93 / 100	2066 ms	215440 KiB

shortcut

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
#include "shortcut.h"
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = (int)(1e6) + 5;
const ll oo = 1e18 + 5;
ll xx[N];
ll x[N];
ll y[N];
int ind[N];
int d[N];
int n,c;
vector < ll > ss;
struct st
{
    ll mxsum,mnsum;
    ll mxdif,mndif;
    st(void)
    {
        mxsum = mxdif = oo;
        mnsum = mndif = -oo;
    }
    st(ll a,ll b,ll c,ll d) : mxsum(a),mnsum(b),mxdif(c),mndif(d) {}
};
const st shit = st(oo,-oo,oo,-oo);
st Comb(st a,st b)
{
    st c;
    c.mxsum = min(a.mxsum,b.mxsum);
    c.mnsum = max(a.mnsum,b.mnsum);
    c.mxdif = min(a.mxdif,b.mxdif);
    c.mndif = max(a.mndif,b.mndif);
    return c;
}
st t[N * 4];
void U(int i,st v)
{
    for (;i;i -= i&(-i))
        t[i] = Comb(t[i],v);
}
st Q(int i)
{
    st ans;
    for (;i <= n;i += i&(-i))
        ans = Comb(ans,t[i]);
    return ans;
}
int F(ll dist)
{
    ll mxsum = oo;
    ll mxdif = oo;
    ll mnsum = -oo;
    ll mndif = -oo;
    for (int i = 1;i <= n;++i)
        t[i] = shit;
    const int SZ = ss.size();
    for (int i = n;i;--i)
    {
        int index = lower_bound(all(ss),y[i] + dist + 1) - ss.begin() + 1;
        if (index <= SZ)
        {
            st cnt = Q(index);
            smin(mxsum,dist - c + y[i] + cnt.mxsum);
            smax(mnsum,c - dist + x[i] + cnt.mnsum);
            smin(mxdif,dist - c + cnt.mxdif - x[i]);
            smax(mndif,c - dist + cnt.mndif - y[i]);
        }
        index = ind[i];
        U(index,st(y[i],x[i],y[i],x[i]));
    }
    set < ll > S;
    for (int i = n;i;--i)
    {
        ll l1 = mndif + xx[i];
        ll r1 = mxdif + xx[i];
        smax(l1,mnsum - xx[i]);
        smin(r1,mxsum - xx[i]);
        auto index = S.lower_bound(l1);
        if (index != S.end() && *index <= r1)
            return 1;
        S.insert(xx[i]);
    }
    return 0;
}
ll find_shortcut(int shit0,vi shit1,vi shit2,int shit3)
{
    n = shit0;
    c = shit3;
    for (int i = 2;i <= n;++i)
        x[i] = x[i - 1] + shit1[i - 2];
    for (int i = 1;i <= n;++i)
        d[i] = shit2[i - 1];
    for (int i = 1;i <= n;++i)
    {
        xx[i] = x[i];
        y[i] = x[i] - d[i];
        x[i] = x[i] + d[i];
    }
    for (int i = 1;i <= n;++i)
        ss.pb(x[i]);
    sort(all(ss));
    ss.resize(unique(all(ss)) - ss.begin());
    for (int i = 1;i <= n;++i)
        ind[i] = lower_bound(all(ss),x[i]) - ss.begin() + 1;
    ll ans = oo;
    for (ll k = 1ll << 60;k;k /= 2)
        if (ans >= k && F(ans - k))
            ans -= k;
    return ans;
}

• 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