oj.uz

Submission #298080

# Submission time Handle Problem Language Result Execution time Memory
298080 2020-09-12T11:17:08 Z SamAnd Sky Walking (IOI19_walk) C++17
0 / 100
 3185 ms 215928 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12024 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 12 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 10 ms 12032 KB Output is correct
10 Correct 12 ms 12160 KB Output is correct
11 Correct 10 ms 12032 KB Output is correct
12 Correct 11 ms 12032 KB Output is correct
13 Correct 11 ms 12032 KB Output is correct
14 Correct 11 ms 12032 KB Output is correct
15 Correct 10 ms 12160 KB Output is correct
16 Incorrect 10 ms 12032 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 1783 ms 124664 KB Output is correct
4 Correct 2195 ms 158656 KB Output is correct
5 Correct 1147 ms 111224 KB Output is correct
6 Correct 1037 ms 99192 KB Output is correct
7 Correct 1152 ms 111640 KB Output is correct
8 Correct 2738 ms 161964 KB Output is correct
9 Correct 1444 ms 116728 KB Output is correct
10 Correct 3185 ms 215928 KB Output is correct
11 Correct 975 ms 75188 KB Output is correct
12 Incorrect 308 ms 25336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 17144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 17144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct
4 Correct 11 ms 12024 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 12 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 10 ms 12032 KB Output is correct
10 Correct 12 ms 12160 KB Output is correct
11 Correct 10 ms 12032 KB Output is correct
12 Correct 11 ms 12032 KB Output is correct
13 Correct 11 ms 12032 KB Output is correct
14 Correct 11 ms 12032 KB Output is correct
15 Correct 10 ms 12160 KB Output is correct
16 Incorrect 10 ms 12032 KB Output isn't correct
17 Halted 0 ms 0 KB -