Submission #1206736

#TimeUsernameProblemLanguageResultExecution timeMemory
1206736thelegendary08Sky Walking (IOI19_walk)C++17
0 / 100
60 ms49076 KiB
#include "walk.h" #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long #define pb push_back #define mp make_pair #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i =k; i<n; i++) #define vi vector<int> #define pii pair<int,int> #define vvi vector<vector<int>> #define vb vector<bool> #define vpii vector<pii> #define mii map<int,int> #define dout(x) cout<<x<<' '<<#x<<endl; #define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl; #define out(x) cout<<x<<endl; #define out2(x,y) cout<<x<<' '<<y<<endl; using namespace std; using namespace __gnu_pbds; const int mxn = (1e5 * 13); vector<vi>adj(mxn); struct event{ int x, d, type; }; bool cmp(event a, event b){ return b.x>a.x; } bool cmp2(pii a, pii b){ if(a.first < b.first)return 1; else if(a.first > b.first)return 0; else return a.second < b.second; } typedef tree<pair<int,int>, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> osp; int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed S, signed g) { //encode a position as h * n + i int n = x.size(); int m = l.size(); /* vvi pts(m); vector<pair<int,pair<pii,int>>>edges; f0r(i,m){ edges.pb(mp(y[i], mp(mp(l[i], r[i]),i))); } sort(edges.rbegin(), edges.rend()); set<int>active; vector<pair<int, pii>> nodes; f0r(i,n){ nodes.pb(mp(h[i], mp(x[i], i))); } sort(nodes.rbegin(), nodes.rend()); int p1 = 0; int p2 = 0; vi nxt(n, -1); while(p1 < m){ if(p2 == n){ auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first); int cur = *it; int d = edges[p1].second.second; while(cur != -1 && cur <= edges[p1].second.first.second){ pts[d].pb(cur); cur = nxt[cur]; } p1++; } else{ if(edges[p1].first > nodes[p2].first){ //compute edge auto it = lower_bound(active.begin(), active.end(), edges[p1].second.first.first); int cur = *it; int d = edges[p1].second.second; while(cur != -1 && cur <= edges[p1].second.first.second){ pts[d].pb(cur); cur = nxt[cur]; } p1++; } else{ auto it = lower_bound(active.begin(), active.end(), nodes[p2].second.second); if(it != active.end())nxt[nodes[p2].second.second] = *it; if(it != active.begin()){ --it; nxt[*it] = nodes[p2].second.second; } active.insert(nodes[p2].second.second); p2++; } } } f0r(i,m){ sort(pts[i].begin(), pts[i].end()); } vector<vpii> ints(n); int cnt = n; f0r(i,m){ for(int k = 0; k<pts[i].size(); k++){ int j = pts[i][k]; ints[j].pb(mp(y[i], cnt)); cnt++; if(k > 0){ int j = pts[i][k-1]; int j2 = pts[i][k]; adj[cnt-1].pb(mp(cnt-2, x[j2] - x[j])); adj[cnt-2].pb(mp(cnt-1, x[j2] - x[j])); } } } f0r(i,n){ ints[i].pb(mp(0, i)); } f0r(i,n){ sort(ints[i].begin(), ints[i].end()); } f0r(i,n){ f0r(j, ints[i].size() - 1){ int h1 = ints[i][j].first; int h2 = ints[i][j+1].first; adj[ints[i][j].second].pb(mp(ints[i][j+1].second, h2-h1)); adj[ints[i][j+1].second].pb(mp(ints[i][j].second, h2-h1)); } } vi dist(mxn, 4e18); dist[s] = 0; priority_queue<pii>q; q.push(mp(0,s)); while(!q.empty()){ int node = q.top().second; q.pop(); for(auto u : adj[node]){ int b = u.first; int w = u.second; if(dist[b] > dist[node] + w){ dist[b] = dist[node] + w; q.push(mp(-dist[b], b)); } } } */ /* out(dist[n + 1]); out(dist[6 * n + 1]); out(dist[6 * n + 2]); out(dist[7*n+2]); out(dist[7*n+6]); out(dist[5*n+6]); out(dist[5*n+5]); */ vector<event>events; f0r(i, m){ events.pb({l[i], i, 0}); events.pb({r[i], i, 1}); } sort(events.begin(), events.end(), cmp); /* for(auto u : events){ cout<<u.x<<'\n'; } */ osp s; f0r(i, events.size()){ if(events[i].type == 0){ s.insert(mp(y[events[i].d], events[i].d)); } else{ int dex = s.order_of_key(mp((int)y[events[i].d], -1LL)); // auto it = lower_bound(s.begin(), s.end(), mp((int)y[events[i].d], -1LL)); if(events[i].d == 2){ // dout(y[events[i].d]); // dout(s.size()); } if(dex != s.size())adj[events[i].d].pb((*s.find_by_order(dex)).second); if(dex != 0){ dex--; adj[events[i].d].pb((*s.find_by_order(dex)).second); } } } /* f0r(i,m){ vout(adj[i]); } */ // vout(adj[mxn-2]); vi dist(mxn, 4e18); dist[mxn-2] = 0; priority_queue<pii>q; f0r(i, m){ if(l[i] == 0){ adj[mxn-2].pb(i); } if(r[i] == n-1){ adj[i].pb(mxn-1); } } q.push(mp(0,mxn-2)); while(!q.empty()){ int node = q.top().second; // dout(node); q.pop(); for(auto u : adj[node]){ int b = u; int w; if(node == mxn-2){ w = y[b]; } else if(b == mxn - 1){ w = y[node]; } else{ w = abs(y[node] - y[b]); } if(dist[b] > dist[node] + w){ dist[b] = dist[node] + w; q.push(mp(-dist[b], b)); } } } if(dist[mxn-1] == 4e18)return -1; else return dist[mxn-1] + x[n-1] - x[0]; return 1; }
#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...