Submission #932301

#	Time	Username	Problem	Language	Result	Execution time	Memory
932301		hmm789	Sky Walking (IOI19_walk)	C++14	24 / 100	4075 ms	866396 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353

const int B = 316;

bool cmp(pair<pair<int, int>, pair<int, int>> a, pair<pair<int, int>, pair<int, int>> b) {
    if(a.second.first/B != b.second.first/B) return a.second.first/B < b.second.first/B;
    else return a.second.second < b.second.second;
}
#undef int
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 a, int b) {
#define int long long
    int n = x.size(), m = l.size(), idx, x1, y1, ht;
    pair<pair<int, int>, pair<int, int>> qry[m];
    for(int i = 0; i < m; i++) qry[i] = {{y[i], i}, {l[i], r[i]}};
    sort(qry, qry+m, cmp);
    int L = 0, R = -1;
    set<pair<int, int>> s;
    vector<int> inters[m];
    for(int i = 0; i < m; i++) {
        ht = qry[i].first.first; idx = qry[i].first.second; x1 = qry[i].second.first; y1 = qry[i].second.second;
        while(L > x1) {
            L--;
            s.insert({h[L], L});
        }
        while(R < y1) {
            R++;
            s.insert({h[R], R});
        }
        while(L < x1) {
            s.erase(s.find({h[L], L}));
            L++;
        }
        while(R > y1) {
            s.erase(s.find({h[R], R}));
            R--;
        }
        for(auto it = s.rbegin(); it != s.rend(); it++) {
            if(it->first < ht) break;
            inters[idx].push_back(it->second);
        }
    }
    map<pair<int, int>, int> mp;
    set<int> tower[n];
    for(int i = 0; i < n; i++) tower[i].insert(0);
    for(int i = 0; i < m; i++) {
        sort(inters[i].begin(), inters[i].end());
        for(int j : inters[i]) {
            tower[j].insert(y[i]);
        }
    }
    idx = 0;
    vector<pair<int, int>> back;
    for(int i = 0; i < n; i++) {
        for(int j : tower[i]) {
            back.push_back({x[i], j});
            mp[{x[i], j}] = idx++;
        }
    }
    vector<int> adj[idx];
    for(int i = 0; i < n; i++) {
        int prv = -1;
        for(int j : tower[i]) {
            if(prv != -1) {
                adj[mp[{x[i], j}]].push_back(mp[{x[i], prv}]);
                adj[mp[{x[i], prv}]].push_back(mp[{x[i], j}]);
            }
            prv = j;
        }
    }
    for(int i = 0; i < m; i++) {
        int prv = -1;
        for(int j : inters[i]) {
            if(prv != -1) {
                adj[mp[{x[j], y[i]}]].push_back(mp[{x[prv], y[i]}]);
                adj[mp[{x[prv], y[i]}]].push_back(mp[{x[j], y[i]}]);
            }
            prv = j;
        }
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int dist[idx];
    memset(dist, -1, sizeof(dist));
    dist[mp[{x[a], 0}]] = 0;
    pq.push({0, mp[{x[a], 0}]});
    while(!pq.empty()) {
        pair<int, int> c = pq.top();
        pq.pop();
        if(dist[c.second] != c.first) continue;
        for(int i : adj[c.second]) {
            int nd = abs(back[i].first-back[c.second].first) + abs(back[i].second-back[c.second].second) + c.first;
            if(dist[i] == -1 || dist[i] > nd) {
                dist[i] = nd;
                pq.push({nd, i});
            }
        }
    }
    return dist[mp[{x[b], 0}]];
#undef int
}

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