제출 #838080

#제출 시각아이디문제언어결과실행 시간메모리
838080penguinmanSky Walking (IOI19_walk)C++17
57 / 100
4091 ms1008752 KiB
#include "walk.h" #include <bits/stdc++.h> #ifndef EVAL #include "grader.cpp" #endif using std::cin; using std::cout; using std::vector; using std::string; using ll = long long; using vi = vector<ll>; using vii = vector<vi>; using pii = std::pair<ll,ll>; #define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++) #define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++) #define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--) #define ln "\n" #define pb emplace_back #define mp std::make_pair #define mtp std::make_tuple #define all(a) a.begin(),a.end() constexpr ll inf = (1ll<<60); template<typename T> struct li_chao_tree{ ll N; vector<std::pair<T,T>> lines; vector<T> x; std::map<ll,ll> rev; li_chao_tree(vector<T> X, T xINF){ N = 1; while(N <= x.size()) N *= 2; lines.resize(2*N, mp(0,inf)); x.resize(N); rep(i,0,N){ if(i < X.size()){ x[i] = X[i]; rev[x[i]] = i; } else x[i] = xINF; } } ll ID(T X){ return rev[X]; } T value(std::pair<T,T> line, T X){ return line.first*X+line.second; } void add_segment(ll a, ll b, std::pair<T,T> line, ll now = 1, ll l = 0, ll r = -1){ if(r == -1) r = N; if(b <= l || r <= a) return; if(a <= l && r <= b){ if(N <= now){ if(value(lines[now], x[l]) > value(line, x[l])) lines[now] = line; return; } ll m = (l+r)/2; bool left = (value(lines[now],x[l]) < value(line, x[l])); bool mid = (value(lines[now],x[m]) < value(line, x[m])); bool right = (value(lines[now],x[r]) < value(line, x[r])); if(left && mid && right){ std::swap(line, lines[now]); return; } if(!left && !mid && !right){ return; } if(left && mid){ std::swap(line, lines[now]); add_segment(a,b,line,now*2+1,m,r); return; } if(mid && right){ std::swap(line, lines[now]); add_segment(a,b,line,now*2,l,m); return; } if(left){ add_segment(a,b,line,now*2,l,m); return; } if(right){ add_segment(a,b,line,now*2+1,m,r); return; } } else{ add_segment(a,b,line,now*2,l,(l+r)/2); add_segment(a,b,line,now*2+1,(l+r)/2,r); } } T calc(ll idx, T X){ T ret = inf; idx += N; while(idx){ ret = std::min(idx, value(lines[idx], X)); idx /= 2; } return ret; } }; template<typename T> struct segment_tree{ ll N; vector<T> node; T valINF; segment_tree(int n, T valINF_): valINF(valINF_){ N = 1; while(N <= n) N *= 2; node.resize(2*N, valINF); } void set(ll idx, T val){ idx += N; node[idx] = val; idx /= 2; while(idx){ node[idx] = compare(node[idx*2], node[idx*2+1]); idx /= 2; } } T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){ if(r == -1) r = N; if(b <= l || r <= a) return valINF; if(a <= l && r <= b) return node[now]; return compare(calc(a,b,now*2,l,(l+r)/2), calc(a,b,now*2+1,(l+r)/2,r)); } T compare(T l, T r){ return std::min(l, r); } }; void dec(std::map<ll,ll> &map, ll el){ map[el]--; if(map[el] == 0) map.erase(el); } ll solve_subtask_1_2(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){ ll N = x.size(); segment_tree<pii> seg(N,mp(inf,inf)); vii edge(N), weight(N); vector<std::map<ll,ll>> rev(N); rep(i,0,N) rev[i][0] = i; ll K = N; rep(i,0,N) seg.set(i, mp(-h[i], i)); rep(i,0,l.size()){ vi data; while(true){ auto el = seg.calc(l[i], r[i]+1); if(-el.first < y[i]) break; data.pb(el.second); seg.set(el.second, mp(inf, inf)); } sort(all(data)); for(auto el: data){ if(!rev[el].count(y[i])){ rev[el][y[i]] = K++; weight.pb(vi()); edge.pb(vi()); } } rep(j,1,data.size()){ ll now = rev[data[j-1]][y[i]]; ll next = rev[data[j]][y[i]]; edge[now].pb(next); edge[next].pb(now); ll cost = x[data[j]]-x[data[j-1]]; weight[now].pb(cost); weight[next].pb(cost); } for(auto el: data){ seg.set(el, mp(-h[el], el)); } } rep(i,0,N){ vi data, height; for(auto el: rev[i]){ data.pb(el.second); height.pb(el.first); } rep(j,1,data.size()){ ll now = data[j-1]; ll next = data[j]; edge[now].pb(next); edge[next].pb(now); ll cost = height[j]-height[j-1]; weight[now].pb(cost); weight[next].pb(cost); } } std::priority_queue<pii> que; vi dist(K, inf); dist[rev[s][0]] = 0; que.push(mp(0,rev[s][0])); while(!que.empty()){ auto el = que.top(); que.pop(); ll now = el.second; if(dist[now] < -el.first) continue; rep(i,0,edge[now].size()){ ll next = edge[now][i]; ll sum = dist[now]+weight[now][i]; if(sum < dist[next]){ dist[next] = sum; que.push(mp(-sum, next)); } } } ll ans = dist[rev[g][0]]; if(ans == inf) ans = -1; return ans; } ll solve_subtask_3_4(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){ ll N = x.size(); vi y_mem; std::map<ll,ll> mem; ll M = 0; { mem[0] = 0; for(auto el: h) mem[el] = 0; for(auto el: y) mem[el] = 0; for(auto &el: mem){ y_mem.pb(el.first); el.second = M++; } } segment_tree<ll> left(M, inf), right(M, inf); vector<std::map<ll,ll>> value(M); rep(i,0,M) value[i][inf] = 1; vii erase_idx(N), erase_val(N); vii add(N); rep(i,0,l.size()){ add[l[i]].pb(i); } rep(t,0,N){ for(auto i: add[t]){ ll val = left.calc(0, mem[y[i]]+1)+y[i]; val = std::min(val, right.calc(mem[y[i]], M)-y[i]); if(t == 0) val = y[i]; value[mem[y[i]]][val]++; left.set(mem[y[i]], (*value[mem[y[i]]].begin()).first-y[i]); right.set(mem[y[i]], (*value[mem[y[i]]].begin()).first+y[i]); erase_idx[r[i]].pb(y[i]); erase_val[r[i]].pb(val); } if(t == N-1) break; rep(i,0,erase_idx[t].size()){ ll Y = erase_idx[t][i]; ll V = erase_val[t][i]; dec(value[mem[Y]], V); left.set(mem[Y], (*value[mem[Y]].begin()).first-Y); right.set(mem[Y], (*value[mem[Y]].begin()).first+Y); } } ll ans = right.calc(0,M)+x[N-1]-x[0]; if(ans >= inf/2) ans = -1; return ans; } 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) { ll N = x.size(); if(s == 0 && g == N-1) return solve_subtask_3_4(x,h,l,r,y,s,g); return solve_subtask_1_2(x,h,l,r,y,s,g); }
#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...