| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 823421 | I_Love_EliskaM_ | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
using ll = long long;
const ll inf = LLONG_MAX;
#define pi pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define int ll
const int sz=1<<30;
struct sgt {
sgt *L, *R; int s;
sgt() {
L=R=NULL; s=inf;
}
void set(int l, int r, int i, int x) {
if (r-l==1) {
s=x; return;
}
int m=(l+r)>>1;
if (i<m) {
if (!L) L=new sgt();
L->set(l,m,i,x);
} else {
if (!R) R=new sgt();
R->set(m,r,i,x);
}
s = min(L?L->s:inf, R?R->s:inf);
}
void set(int i, int x) {
set(0,sz,i,x);
}
int query(int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return inf;
if (lx<=l && r<=rx) return s;
int m=(l+r)>>1;
int lq=L?L->query(l,m,lx,rx):inf;
int rq=R?R->query(m,r,lx,rx):inf;
return min(lq,rq);
}
int query(int l, int r) {
return query(0,sz,l,r);
}
};
const int N=1e5+55;
vector<pi> adj[10*N];
ll d[10*N];
map<int,int> c[N]; int _z=0; const int Z=1e9+5;
int ind(int x, int y) {
if (c[x].count(y)) return c[x][y];
return c[x][y]=_z++;
}
#undef int
ll p12(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
int n=x.size(), m=l.size();
vector<vector<int>> g1(n);
vector<vector<int>> g2(m);
g1[s].pb(0);
g1[g].pb(0);
vector<pi> v;
forn(i,n) v.pb({h[i],i});
forn(i,m) v.pb({y[i],-i-1});
sort(rall(v));
set<int> st;
for(auto&z:v) {
int y=z.f, i=z.s;
if (i>=0) {
st.insert(i); continue;
}
i*=-1; --i;
auto it=st.upper_bound(l[i]);
vector<int> v;
while (1) {
int j=*it;
v.pb(j);
if (j==r[i]) break;
++it;
}
if (v.size() > 10 && max(n,m)>50) return -2;
g1[l[i]].pb(y);
int last=l[i];
for(auto&j:v) {
adj[ind(last,y)].pb({ind(j,y),x[j]-x[last]});
adj[ind(j,y)].pb({ind(last,y),x[j]-x[last]});
g1[j].pb(y);
last=j;
}
}
forn(i,n) {
sort(all(g1[i]));
int sz=g1[i].size();
forn(j,sz-1) {
adj[ind(i,g1[i][j])].pb({ind(i,g1[i][j+1]),g1[i][j+1]-g1[i][j]});
adj[ind(i,g1[i][j+1])].pb({ind(i,g1[i][j]),g1[i][j+1]-g1[i][j]});
}
}
forn(i,_z) d[i]=inf;
priority_queue<pair<ll,ll>> q; q.push({0,ind(s,0)});
while(q.size()) {
auto it=q.top(); q.pop();
ll di=-it.f, u=it.s;
if (d[u]<=di) continue;
d[u]=di;
//assert(adj[u].size()<=4);
for(auto&e:adj[u]) {
int v=e.f, w=e.s;
if (d[v]!=inf) continue;
q.push({-di-w,v});
}
}
if (d[ind(g,0)]==inf) return -1;
return d[ind(g,0)];
}