Submission #472910

#	Time	Username	Problem	Language	Result	Execution time	Memory
472910		dxz05	Sky Walking (IOI19_walk)	C++14	24 / 100	4116 ms	838256 KiB

walk

#pragma GCC optimize("Ofast,O2,O3")
#pragma GCC target("avx,avx2")

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MP make_pair

const int MAXN = 5e6 + 3e2;

int table[MAXN][20], Log[MAXN];

void build_table(vector<int> &h){
    int n = h.size();
    for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;

    for (int i = 0; i < 20; i++){
        for (int j = 0; j < n; j++){
            if (i == 0){
                table[j][i] = h[j];
            } else {
                table[j][i] = max(table[j][i - 1], table[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
}

int get(int l, int r){
    if (l > r) return 0;
    int x = Log[r - l + 1];
    return max(table[l][x], table[r - (1 << x) + 1][x]);
}

void sort(vector<int> &l, vector<int> &r, vector<int> &y){
    vector<pair<int, pair<int, int>>> vec(y.size());
    for (int i = 0; i < y.size(); i++){
        vec[i] = MP(y[i], MP(l[i], r[i]));
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < y.size(); i++){
        y[i] = vec[i].first;
        l[i] = vec[i].second.first;
        r[i] = vec[i].second.second;
    }
}

map<int, int> mp[MAXN];
int next_id = 0;
vector<pair<int, int>> points[MAXN];

int id(int i, int h){
    if (mp[i].find(h) != mp[i].end()) return mp[i][h];
    return mp[i][h] = next_id++;
}

vector<pair<int, int>> g[MAXN];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int start, int finish) {
    int n = x.size(), m = y.size();
    sort(l, r, y);

    build_table(h);

    for (int i = 0; i < n; i++){
        points[i].emplace_back(id(i, 0), 0);
    }

    for (int i = 0; i < m; i++){
        //cout << l[i] << ' ' << r[i] << ' ' << y[i] << endl;
        points[l[i]].emplace_back(id(l[i], y[i]), y[i]);
        int last = l[i];
        while (last < r[i]){
            int j;

            int L = last + 1, R = r[i];
            while (L <= R){
                int M = (L + R) >> 1;
                if (get(last + 1, M) >= y[i]){
                    j = M;
                    R = M - 1;
                } else L = M + 1;
            }

            int a = id(j, y[i]);
            points[j].emplace_back(a, y[i]);

            if (j > l[i]) {
                int b = id(last, y[i]);
                g[a].emplace_back(b, x[j] - x[last]);
                g[b].emplace_back(a, x[j] - x[last]);
            }

            last = j;
        }
    }

    for (int i = 0; i < n; i++){
        if (points[i].back().second != h[i]) points[i].emplace_back(id(i, h[i]), h[i]);
//        cout << i << endl;
        for (int j = 1; j < points[i].size(); j++){
//            cout << points[i][j].first << ' ' << points[i][j].second << endl;
            int a = points[i][j - 1].first, b = points[i][j].first, w = points[i][j].second - points[i][j - 1].second;
            g[a].emplace_back(b, w);
            g[b].emplace_back(a, w);
        }
    }

    int k = next_id;
    vector<ll> d(k, 1e18);
    vector<bool> processed(k, false);
    d[start] = 0;

    priority_queue<pair<ll, int>> pq;
    pq.push(MP(0, start));

    while (!pq.empty()){
        int v = pq.top().second; pq.pop();
        if (processed[v]) continue;
        processed[v] = true;

        for (auto e : g[v]){
            int u = e.first, w = e.second;
            assert(w >= 0);
            if (d[u] > d[v] + w){
                d[u] = d[v] + w;
                pq.push(MP(-d[u], u));
            }
        }

    }

    if (!processed[finish]) return -1;

	return d[finish];
}

Compilation message (stderr)

walk.cpp: In function 'void sort(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
walk.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
walk.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < y.size(); i++){
      |                     ~~^~~~~~~~~~
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:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int j = 1; j < points[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~
walk.cpp:77:21: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         while (last < r[i]){

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