Submission #987231

#	Time	Username	Problem	Language	Result	Execution time	Memory
987231		AdamGS	Sky Walking (IOI19_walk)	C++17	100 / 100	2918 ms	229812 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
vector<ll>T, H;
vector<pair<ll,ll>>V[20*LIM];
set<pair<ll,ll>>S;
map<pair<ll,ll>,ll>mp;
ll tr[4*LIM], odl[20*LIM], n, N=1, akt;
void upd(int l, int r, ll x) {
  l+=N; r+=N;
  tr[l]=max(tr[l], x);
  tr[r]=max(tr[r], x);
  while(l/2!=r/2) {
    if(l%2==0) tr[l+1]=max(tr[l+1], x);
    if(r%2==1) tr[r-1]=max(tr[r-1], x);
    l/=2; r/=2;
  }
}
ll cnt(int v) {
  v+=N;
  ll ans=tr[v];
  while(v) {
    ans=max(ans, tr[v]);
    v/=2;
  }
  return ans;
}
void kraw(pair<ll,ll>a, pair<ll,ll>b) {
  if(mp.find(a)==mp.end()) {
    mp[a]=akt++;
    S.insert({a.nd, a.st});
  }
  if(mp.find(b)==mp.end()) {
    mp[b]=akt++;
    if(S.find({b.nd, b.st})==S.end() && b.nd!=0) {
      auto it=S.lower_bound({b.nd, b.st});
      if(it!=S.end()) {
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
      if(it!=S.begin()) {
        --it;
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
    }
    S.insert({b.nd, b.st});
  }
  ll o=abs(a.st-b.st)+abs(a.nd-b.nd);
  V[mp[a]].pb({mp[b], o});
  V[mp[b]].pb({mp[a], o});
}
void dodaj(ll l, ll r, ll y) {
  kraw({T[l], y}, {T[r], y});
  kraw({T[l], y}, {T[l], cnt(l)});
  kraw({T[r], y}, {T[r], cnt(r)});
  upd(l, r, y);
}
ll ind(vector<ll>&X, ll y) {
  ll po=0, ko=(ll)X.size()-1;
  while(po<ko) {
    ll sr=(po+ko+1)/2;
    if(H[X[sr]]>=y) po=sr; else ko=sr-1;
  }
  return X[po];
}
ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
  if(s>g) swap(s, g);
  n=x.size();
  T.resize(n);
  H.resize(n);
  rep(i, n) T[i]=x[i];
  rep(i, n) H[i]=h[i];
  while(N<n) N*=2;
  vector<pair<ll,pair<ll,ll>>>P;
  rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
  mp[{x[s], 0}]=0;
  mp[{x[g], 0}]=1;
  akt=2;
  sort(all(P));
  vector<ll>X, lewos, lewog, prawos, prawog;
  rep(i, n) {
    while(X.size()>0 && h[i]>=h[X.back()]) X.pop_back();
    X.pb(i);
    if(i==s) lewos=X;
    if(i==g) lewog=X;
  }
  X.clear();
  for(int i=n-1; i>=0; --i) {
    while(X.size()>0 && h[i]>=h[X.back()]) X.pop_back();
    X.pb(i);
    if(i==s) prawos=X;
    if(i==g) prawog=X;
  }
  for(auto i : P) {
    if(i.nd.nd<=s || g<=i.nd.st || s<=i.nd.st && i.nd.nd<=g) {
      dodaj(i.nd.st, i.nd.nd, i.st);
      continue;
    }
    ll a=i.nd.st, b=ind(lewos, i.st), c=ind(prawos, i.st), d=ind(lewog, i.st), e=ind(prawog, i.st), f=i.nd.nd;
    if(i.nd.nd<g) {
      dodaj(a, b, i.st);
      dodaj(b, c, i.st);
      dodaj(c, f, i.st);
      continue;
    }
    if(s<i.nd.st) {
      dodaj(a, d, i.st);
      dodaj(d, e, i.st);
      dodaj(e, f, i.st);
      continue;
    }
    dodaj(a, b, i.st);
    dodaj(b, c, i.st);
    if(c<d) dodaj(c, d, i.st);
    dodaj(d, e, i.st);
    dodaj(e, f, i.st);
  }
  rep(i, akt+1) odl[i]=INF;
  priority_queue<pair<ll,ll>>q;
  q.push({0, 0});
  while(!q.empty()) {
    ll o=-q.top().st, p=q.top().nd; q.pop();
    if(odl[p]<=o) continue;
    odl[p]=o;
    for(auto i : V[p]) q.push({-o-i.nd, i.st});
  }
  if(odl[1]==INF) return -1;
  return odl[1];
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
walk.cpp:84:3: note: in expansion of macro 'rep'
   84 |   rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
      |   ^~~
walk.cpp:104:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  104 |     if(i.nd.nd<=s || g<=i.nd.st || s<=i.nd.st && i.nd.nd<=g) {
      |                                    ~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43