이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |