| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 296703 | Leonardo16 | Sky Walking (IOI19_walk) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "walk.h"
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("avx2")
//#define int long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define fst first
#define scd second
#define vi vector<ll>
#define vii vector<ii>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
/// Functions
#define db(x) cerr << #x << ": " << (x) << '\n';
#define random() __builtin_ia32_rdtsc()
#define lg2(x) 31-__builtin_clz(x)
#define lg2ll(x) 63-__builtin_clzll(x)
#define pi acos(-1)
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
#define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;}
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
/// Red-Black Tree Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long , null_type , less<long long> , rb_tree_tag , tree_order_statistics_node_update > ordered_set;
//#define less_than(n) order_of_key(n)
//#define en_pos(n) find_by_order(n)
/// Prime numbers 173,179,311,331,737,1009,2011,2027,3079,4001,100003
///=====================================================================
vii G[200005];
struct build{
ll x,h;
bool operator<(const build &b){
return x<b.x;
}
ll id,id1;
vector<ll>cuts;
};
struct walk{
ll y,l,r;
};
map<ll,build>bu;
map<ll,vi >mp;
map<ll,ll>sk;
ll dist[200005];
void dijkstra(ll s){
for(ll i=0;i<200005;i++){
dist[i]=1e18;
}
dist[s]=0;
priority_queue< pair<ll,ll> >q;
q.push({0,s});
while(!q.empty()){
pair<ll,ll> nxt=q.top();q.pop();
ll d=-nxt.fst;
ll u=nxt.scd;
if(d>dist[u])continue;
for(auto v:G[u]){
if(d+v.scd<dist[v.fst]){
dist[v.fst]=d+v.scd;
q.push({-dist[v.fst],v.fst});
}
}
}
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, ll s, ll g) {
for(ll i=0;i<x.sz();i++){
build b;
b.x=x[i];
b.h=h[i];
b.id=i+1;
bu[b.x]=b;
sk[b.x]=b.h;
mp[b.x].clear();
}
for(ll i=0;i<l.sz();i++){
walk w;
w.l=l[i];
w.r=r[i];
w.y=y[i];
mp[l[i]].pb(y[i]);
mp[r[i]+1].pb(-y[i]);
}
map<ll,ll >m2;
ll wr=x.sz()+1;
map<ll,ii>prevv;
for(auto it:mp){
sort(rall(mp[it.fst]));
}
for(auto it:mp){
// cout<<"----------> "<<it.fst<<fl;
for(auto i2:it.scd){
// cout<<"+"<<i2<<fl;
if(i2>0){
m2[i2]++;
}else{
m2[abs(i2)]--;
if(m2[abs(i2)]<=0){prevv[abs(i2)].fst=0;m2.erase(abs(i2));}
}
}
if(sk[it.fst]!=0){
ll prev=0;
vi tp,tp2;
while(m2.sz()){
ll mi=(*m2.begin()).fst;
tp2.pb(m2[mi]);
m2.erase(mi);
tp.pb(mi);
if(mi<=sk[it.fst]){
// cout<<"-->"<<it.fst<<" "<<mi<<fl;
build b=bu[it.fst];
if(prev==0){
G[b.id].pb({wr,mi});
G[wr].pb({b.id,mi});
}else{
G[wr-1].pb({wr,mi-prev});
G[wr].pb({wr-1,mi-prev});
}
if(prevv[mi].fst!=0){
G[wr].pb({prevv[mi].fst,it.fst-prevv[mi].scd});
G[prevv[mi].fst].pb({wr,it.fst-prevv[mi].scd});
}
prevv[mi]={wr,it.fst};
prev=mi;
wr++;
}else{
break;
}
}
for(ll i=0;i<tp.sz();i++){
m2[ tp[i] ] =tp2[i];
}
}
}
dijkstra(s+1);
if(dist[g+1]==1e18)return -1;
return dist[g+1];
}