oj.uz

Submission #298075

# Submission time Handle Problem Language Result Execution time Memory
298075 2020-09-12T11:06:34 Z SamAnd Sky Walking (IOI19_walk) C++17
0 / 100
 3185 ms 219512 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(y[i]);
        v[r[i]].push_back(-y[i]);
    }

    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)
        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 10 ms 12032 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 12 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 9 ms 12160 KB Output is correct
12 Correct 10 ms 12032 KB Output is correct
13 Correct 8 ms 12032 KB Output is correct
14 Correct 9 ms 12032 KB Output is correct
15 Correct 11 ms 12032 KB Output is correct
16 Incorrect 9 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 9 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 1795 ms 126712 KB Output is correct
4 Correct 2193 ms 162804 KB Output is correct
5 Correct 1124 ms 114680 KB Output is correct
6 Correct 1006 ms 102636 KB Output is correct
7 Correct 1124 ms 115064 KB Output is correct
8 Correct 2865 ms 164044 KB Output is correct
9 Correct 1485 ms 120392 KB Output is correct
10 Correct 3185 ms 219512 KB Output is correct
11 Correct 957 ms 77688 KB Output is correct
12 Incorrect 305 ms 29432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 14840 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 10 ms 12032 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 12 ms 12160 KB Output is correct
7 Correct 10 ms 12160 KB Output is correct
8 Correct 11 ms 12160 KB Output is correct
9 Correct 10 ms 12160 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 9 ms 12160 KB Output is correct
12 Correct 10 ms 12032 KB Output is correct
13 Correct 8 ms 12032 KB Output is correct
14 Correct 9 ms 12032 KB Output is correct
15 Correct 11 ms 12032 KB Output is correct
16 Incorrect 9 ms 12032 KB Output isn't correct
17 Halted 0 ms 0 KB -