Submission #823866

#	Time	Username	Problem	Language	Result	Execution time	Memory
823866		vjudge1	Sky Walking (IOI19_walk)	C++17	0 / 100	1693 ms	167032 KiB

walk

#include "walk.h"

#include <bits/stdc++.h>

using namespace std;

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 g) {
    vector<int> A = h, B = h;
    for (int i = s + 1; i < A.size(); i++) {
        A[i] = max(A[i - 1], A[i]);
    }
    for (int i = s - 1; i >= 0; i--) {
        A[i] = max(A[i + 1], A[i]);
    }
    for (int i = g + 1; i < B.size(); i++) {
        B[i] = max(B[i - 1], B[i]);
    }
    for (int i = g - 1; i >= 0; i--) {
        B[i] = max(B[i + 1], B[i]);
    }

    int m = 0;
/*
    int m = l.size();
    for (int i = 0; i < m; i++) {
        auto get = [&](int x, vector<int> &v, int h) -> tuple<int, int> {
            int l = x, r = v.size() - 1;
            while (l < r) {
                int m = (l + r) / 2;
                if (v[m] >= h) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            int B = l;

            l = 0, r = x;
            while (l < r){
                int m = (l + r) / 2;
                if (v[m + 1] >= h) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            return {l, B};
        };

        vector<int> v = {l[i], r[i]};
        if (l[i] < s && s < r[i]) {
            auto [x, y2] = get(s, A, y[i]);
            v.push_back(x);
            v.push_back(y2);
        }
        if (l[i] < g && g < r[i]) {
            auto [x, y2] = get(g, B, y[i]);
            v.push_back(x);
            v.push_back(y2);
        }
        sort(v.begin(), v.end());
        for (int j = 1; j < v.size(); j++) {
            if (v[j] != v[j - 1]) {
                l.push_back(v[j - 1]);
                r.push_back(v[j]);
                y.push_back(y[i]);
            }
        }
    }
*/

    long long inf = 1e18;
    vector<map<int, long long>> d(x.size());
    vector<map<int, vector<pair<int, int>>>> V(x.size());
    unordered_map<int, vector<int>> id;

    for (int i = 0; i < x.size(); i++) {
        d[i][0] = inf;
    }
    vector<vector<int>> gg;
    for (int i = m; i < l.size(); i++) {
        gg.push_back({l[i], y[i]});
        gg.push_back({r[i], y[i]});
        gg.push_back({l[i], -1, y[i]});
        gg.push_back({r[i] + 1, -2, y[i]});
    }
    sort(gg.begin(), gg.end());

    map<int, int> S;
    for (auto& shit: gg) {
        if (shit[1] == -1) {
            S[shit[2]]++;
        } else if (shit[1] == -2) {
            S[shit[2]]--;
            if (S[shit[2]] == 0) {
                S.erase(shit[2]);
            }
        } else {
            d[shit[0]][shit[1]] = inf;
            auto p = S.lower_bound(shit[1]);
            if (p != S.begin()) {
                p--;
                d[shit[0]][p->first] = inf;
            }
        }
    }

    d[s][0] = 0;

    for (int i = 0; i < x.size(); i++) {
        int last = 0;
        for (auto p: d[i]) {
            id[p.first].push_back(i);
            //cout << i << " " << p.first << " " << i << " " << last << "\n";
            V[i][p.first].push_back({i, last});
            V[i][last].push_back({i, p.first});
            last = p.first;
        }
    }
    unordered_map<int, vector<int>> sid = id;
    for (auto&p : sid) {
        for (int j = 0; j < p.second.size(); j++) {
            p.second[j] = 0;
        }
        p.second.push_back(0);
    }
    for (int i = m; i < l.size(); i++) {
        // l[i], r[i]
        sid[y[i]][lower_bound(id[y[i]].begin(), id[y[i]].end(), l[i]) - id[y[i]].begin()]++;
        sid[y[i]][lower_bound(id[y[i]].begin(), id[y[i]].end(), r[i]) - id[y[i]].begin()]--;
    }
    //cout << "L ";
    //for (int i: id[5]) {
    //    cout << i << " ";
    //}
    //cout << "\n";
    for (auto&p : id) {
        auto shit = sid[p.first];
        for (int j = 0; j + 1 < shit.size(); j++) {
            shit[j + 1] += shit[j];
            if (shit[j]) {
                //cout << p.second[j] << " " << p.first << " " << p.second[j + 1] << " " << p.first << "\n";
                V[p.second[j]][p.first].push_back({p.second[j + 1], p.first});
                V[p.second[j + 1]][p.first].push_back({p.second[j], p.first});
            }
        }
    }

    auto dist = [&](int x1, int y1, int x2, int y2) -> long long {
        return (long long)abs(x[x1] - x[x2]) + abs(y1 - y2);
    };

    set<pair<long long, pair<int, int>>> f;
    f.insert({0, {s, 0}});
    while (!f.empty()) {
        int a = f.begin()->second.first;
        int b = f.begin()->second.second;
        f.erase(f.begin());
        for (auto to: V[a][b]) {
            int na = to.first, nb = to.second;
            if (d[a][b] + dist(a, b, na ,nb) < d[na][nb]) {
                f.erase({d[na][nb], {na, nb}});
                d[na][nb] = d[a][b] + dist(a, b, na ,nb);
                f.insert({d[na][nb], {na, nb}});
            }
        }
    }

    return d[g][0];
}

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:9:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = s + 1; i < A.size(); i++) {
      |                         ~~^~~~~~~~~~
walk.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = g + 1; i < B.size(); i++) {
      |                         ~~^~~~~~~~~~
walk.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~
walk.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = m; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
walk.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~
walk.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int j = 0; j < p.second.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
walk.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = m; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
walk.cpp:139:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int j = 0; j + 1 < shit.size(); j++) {
      |                         ~~~~~~^~~~~~~~~~~~~

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