oj.uz

Submission #298086

# Submission time Handle Problem Language Result Execution time Memory
298086 2020-09-12T11:35:06 Z SamAnd Sky Walking (IOI19_walk) C++17
0 / 100
 3221 ms 215708 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;
}

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

    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:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         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 10 ms 12032 KB Output is correct
4 Correct 11 ms 12032 KB Output is correct
5 Correct 11 ms 12160 KB Output is correct
6 Correct 11 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 11 ms 12080 KB Output is correct
10 Correct 11 ms 12160 KB Output is correct
11 Correct 10 ms 12032 KB Output is correct
12 Correct 10 ms 12032 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 10 ms 12032 KB Output is correct
15 Correct 10 ms 12032 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 12 ms 12032 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 1778 ms 124728 KB Output is correct
4 Correct 2237 ms 158712 KB Output is correct
5 Correct 1124 ms 111224 KB Output is correct
6 Correct 915 ms 99108 KB Output is correct
7 Correct 1122 ms 111688 KB Output is correct
8 Correct 2752 ms 162120 KB Output is correct
9 Correct 1364 ms 116832 KB Output is correct
10 Correct 3221 ms 215708 KB Output is correct
11 Correct 1006 ms 74948 KB Output is correct
12 Incorrect 464 ms 36344 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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