Submission #298080

#	Time	Username	Problem	Language	Result	Execution time	Memory
298080		SamAnd	Sky Walking (IOI19_walk)	C++17	0 / 100	3185 ms	215928 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 = 1000000009000000009;

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;
}

vector<int> v[N];
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))
    {
    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;
        }
    }
    }

    for (int i = 0; i < m; ++i)
    {
        v[l[i]].push_back((i + 1));
        v[r[i]].push_back((-i - 1));
    }

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

    s.insert(m_p(0, -1));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < sz(v[i]); ++j)
        {
            int u = v[i][j];
            if (u > 0)
            {
                --u;
                int yy = y[u];
                int y = yy;
                auto it = s.upper_bound(m_p(y, -1));
                dp[u] = INF;
                if (it != s.end())
                    dp[u] = min(dp[u], dp[it->se] + abs(y - it->fi));
                if (!s.empty() && it != s.begin())
                {
                    --it;
                    dp[u] = min(dp[u], dp[it->se] + abs(y - it->fi));
                }
                s.insert(m_p(y, u));
            }
        }
        if (i == n - 1)
            break;
        for (int j = 0; j < sz(v[i]); ++j)
        {
            int u = v[i][j];
            if (u < 0)
            {
                u *= -1;
                --u;
                int yy = y[u];
                int y = yy;
                s.erase(m_p(y, u));
                auto it = s.upper_bound(m_p(y, -1));
                if (it != s.end())
                    dp[it->se] = min(dp[it->se], dp[u] + abs(it->fi - y));
                if (!s.empty() && it != s.begin())
                {
                    --it;
                    dp[it->se] = min(dp[it->se], dp[u] + abs(it->fi - y));
                }
            }
        }
        if (!i)
            s.erase(m_p(0, -1));
    }
    ll ans = INF;
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        ans = min(ans, dp[it->se] + x[n - 1] + it->fi);
    }
    if (ans == INF)
        return -1;
    return ans;
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         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