Submission #298250

#	Time	Username	Problem	Language	Result	Execution time	Memory
298250		SamAnd	Sky Walking (IOI19_walk)	C++17	0 / 100	278 ms	55796 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;
const ll INF = 2000000009000000009;

int n, m;

map<int, vector<int> > g[N];
set<pair<int, int> > c;
set<int> s[N];

pair<int, int> maxu[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        maxu[pos] = m_p(y, x);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    maxu[pos] = max(maxu[pos * 2], maxu[pos * 2 + 1]);
}

pair<int, int> qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return m_p(-1, -1);
    if (tl == l && tr == r)
        return maxu[pos];
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

struct ban
{
    pair<int, int> u;
    ll d;
    ban(){}
    ban(pair<int, int> u, ll d)
    {
        this->u = u;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

ll solv0(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int S, int F)
{
    n = sz(x);
    m = sz(y);

    for (int i = 0; i < 20; ++i)
    {
        s[i].clear();
        g[i].clear();
    }
    c.clear();

    for (int i = 0; i < n; ++i)
        ubd(0, n - 1, i, h[i], 1);

    for (int i = 0; i < m; ++i)
    {
        vector<int> v;
        while (1)
        {
            pair<int, int> u = qry(0, n - 1, l[i], r[i], 1);
            if (u.fi < y[i])
                break;
            v.push_back(u.se);
            ubd(0, n - 1, u.se, -1, 1);
        }
        sort(all(v));
        for (int j = 0; j < sz(v); ++j)
        {
            s[v[j]].insert(y[i]);
            ubd(0, n - 1, v[j], h[v[j]], 1);
        }
        for (int j = 0; j < sz(v) - 1; ++j)
        {
            g[v[j]][y[i]].push_back(v[j + 1]);
            g[v[j + 1]][y[i]].push_back(v[j]);
        }
    }
    s[S].insert(0);
    s[F].insert(0);

    priority_queue<ban> q;
    q.push(ban(m_p(S, 0), 0));
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
                return -1;
            t = q.top();
            q.pop();
        } while (c.find(t.u) != c.end());
        c.insert(t.u);
        if (t.u == m_p(F, 0))
            return t.d;
        for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
        {
            ban h = ban(m_p(g[t.u.fi][t.u.se][i], t.u.se), t.d);
            h.d += abs(x[t.u.fi] - x[h.u.fi]);
            q.push(h);
        }
        auto it = s[t.u.fi].find(t.u.se);
        if (it != (--s[t.u.fi].end()))
        {
            ++it;
            ban h = ban(m_p(t.u.fi, *it), t.d + *it - t.u.se);
            q.push(h);
            --it;
        }
        if (it != s[t.u.fi].begin())
        {
            --it;
            ban h = ban(m_p(t.u.fi, *it), t.d + t.u.se - *it);
            q.push(h);
            ++it;
        }
    }
}

map<int, vector<pair<int, int> > > mp;
vector<int> v[N];
ll solv1(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int S, int F)
{
    n = sz(x);
    m = sz(y);

    for (int i = 0; i < 20; ++i)
        v[i].clear();
    mp.clear();

    for (int i = 0; i < m; ++i)
    {
        mp[y[i]].push_back(m_p(l[i], 1));
        mp[y[i]].push_back(m_p(r[i], -1));
    }
    for (auto it = mp.begin(); it != mp.end(); ++it)
    {
        sort(all(it->se));
        int q = 0;
        vector<pair<int, int> > vv;
        for (int i = 0; i < sz(it->se); ++i)
        {
            q += it->se[i].se;
            if (q && it->se[i].fi != it->se[i + 1].fi)
            {
                if (vv.empty())
                    vv.push_back(m_p(it->se[i].fi, it->se[i + 1].fi));
                else
                {
                    if (it->se[i].fi == vv.back().se)
                        vv.back().se = it->se[i + 1].fi;
                    else
                        vv.push_back(m_p(it->se[i].fi, it->se[i + 1].fi));
                }
            }
        }
        for (int i = 0; i < sz(vv); ++i)
        {
            v[vv[i].fi].push_back(it->fi);
            v[vv[i].se].push_back(-it->fi);
        }
    }

    map<int, ll> dp;
    set<int> s;

    s.insert(0);
    dp[0] = 0;
    v[0].push_back(0);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < sz(v[i]); ++j)
        {
            int y = v[i][j];
            if (y > 0)
            {
                auto it = s.upper_bound(y);
                dp[y] = INF;
                if (it != s.end())
                    dp[y] = min(dp[y], dp[*it] + abs(y - *it));
                if (!s.empty() && it != s.begin())
                {
                    --it;
                    dp[y] = min(dp[y], dp[*it] + abs(y - *it));
                }
                s.insert(y);
            }
        }
        if (i == n - 1)
            break;
        for (int j = 0; j < sz(v[i]); ++j)
        {
            int y = v[i][j];
            if (y <= 0)
            {
                y *= -1;
                s.erase(y);
                auto it = s.upper_bound(y);
                if (it != s.end())
                    dp[*it] = min(dp[*it], dp[y] + abs(*it - y));
                if (!s.empty() && it != s.begin())
                {
                    --it;
                    dp[*it] = min(dp[*it], dp[y] + abs(*it - y));
                }
            }
        }
    }
    ll ans = INF;
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        ans = min(ans, dp[*it] + x[n - 1] + *it);
    }
    if (ans == INF)
    {
        //while ((double)clock() / CLOCKS_PER_SEC < 2.0){}
        return -1;
    }
    return ans;
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int S, int F)
{
    n = sz(x);
    m = sz(y);

    if (!(S == 0 && F == n - 1))
        return solv0(x, h, l, r, y, S, F);

    //return solv1(x, h, l, r, y, S, F);
    if (solv0(x, h, l, r, y, S, F) != solv1(x, h, l, r, y, S, F))
    {
        solv1(x, h, l, r, y, S, F);
        assert(false);
    }
    return 0;
}

Compilation message (stderr)

walk.cpp: In function 'll solv0(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:118:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i = 0; i < g[t.u.fi][t.u.se].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43