Submission #1048884

#TimeUsernameProblemLanguageResultExecution timeMemory
1048884fuad27Sky Walking (IOI19_walk)C++17
0 / 100
4058 ms433968 KiB
#include "walk.h" #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); 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 st, int ed) { int n = h.size(); int m = y.size(); vector<int> bl; vector<int> br(m); bl.resize(n); iota(bl.begin(),bl.end(), 0); iota(br.begin(),br.end(), 0); sort(bl.begin(), bl.end(), [&](int u, int v) -> bool { return h[u] > h[v]; }); sort(br.begin(), br.end(), [&](int u, int v) -> bool { return y[u] > y[v]; }); int p1 = 0; set<int> s; map<int,vector<int>> mp; map<int,vector<int>> coords; vector<vector<pair<int,long long>>> g; map<pair<int,int>, int> cmp; auto add = [&](int x, int y) -> int { if(cmp.find(pair<int,int>(x, y))!=cmp.end())return cmp[{x, y}]; cmp[{x,y}]=g.size(); coords[x].push_back(y); g.push_back({}); return cmp[{x,y}]; }; for(int i = 0;i<m;i++) { while(p1 < n and h[bl[p1]] >= y[br[i]]) { mp[x[bl[p1]]].push_back(bl[p1]); s.insert(x[bl[p1++]]); } int prev=-1; for(auto it = s.lower_bound(x[l[br[i]]]);it!=s.end();it++) { if((*it) > x[r[br[i]]])break; int at = (*it); // cout << y[br[i]] << " " << at << endl; if(coords[at].size()) coords[at].push_back(y[br[i]]); else coords[at].push_back(0); add(at, y[br[i]]); add(at, 0); if(prev!=-1) { g[add(prev, y[br[i]])].push_back({add(at, y[br[i]]), abs(at-prev)}); g[add(at, y[br[i]])].push_back({add(prev, y[br[i]]), abs(at-prev)}); } prev=at; } } for(auto &i:coords) { sort(i.second.begin(), i.second.end()); for(int j = 1;j<(int)(i.second).size();j++) { // cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl; // cout << i.first << " " << i.second[j-1] << " " << i.second[j] << endl; g[add(i.first, i.second[j-1])].push_back({add(i.first, i.second[j]), abs(i.second[j]-i.second[j-1])}); g[add(i.first, i.second[j])].push_back({add(i.first, i.second[j-1]), abs(i.second[j]-i.second[j-1])}); } } // cout << endl; priority_queue<pair<long long,int>> pq; pq.push(pair<long long, int>(0ll, add(x[st], 0))); vector<long long> dist(g.size(), (long long)2e18); dist[add(x[st], 0)] = 0; map<int, pair<int,int>> revs; for(auto i:cmp) { revs[i.second] = i.first; } while(pq.size()) { int at = pq.top().second; // cout << revs[at].first << " " << revs[at].second << " " << dist[at] << endl; pq.pop(); for(auto [to, w]:g[at]){ if(dist[to] > dist[at] + w) { dist[to] = dist[at]+w; pq.push(pair<long long, int> (-dist[to], to)); } } } return dist[add(x[ed], 0)]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...