Submission #685670

#	Time	Username	Problem	Language	Result	Execution time	Memory
685670		cadmiumsky	Sky Walking (IOI19_walk)	C++14	100 / 100	2328 ms	301140 KiB

walk

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<ll,ll>;
//using tii = tuple<int,int,int>;

struct tii {
  int first, second, ind;
  tii(int x, int y, int i) : first(x), second(y), ind(i) {;}
  tii() : first(-1), second(-1), ind(-1) {;}
  bool operator == (const tii& x) const { 
    return first == x.first && second == x.second;
  }
};


const int nmax = 1e5 + 5;
const ll inf = 1e18 + 5;

map<int, vector<pii>, greater<int>> segm;
map<int, vector<int>, greater<int>> columns;
vector<pii> buildings;

void repair(vector<pii> &v) {
  sort(all(v));
  int last = 0;
  for(int i = 1; i < sz(v); i++) {
    if(v[last].second == v[i].first) {
      v[last].second = v[i].second;
      v[i].second = -1;
    }
    else
      last = i;
  }
  v.resize(distance(v.begin(), stable_partition(all(v), [](auto x) { return x.second != -1; })));
}

namespace PointsG {
  vector<tii> pts;
  vector<vector<pii>> g;
  
  void addedge(int x, int y, int w) {
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }
  void add(int x, int y) {
    //cerr << "+ " << x << ' ' << y< '\n';
    pts.emplace_back(x, y, sz(pts));
  }

  void init() {
    sort(all(pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
    pts.resize(distance(pts.begin(), unique(all(pts))));
    for(int i = 0; i < sz(pts); i++)
      pts[i].ind = i;
    g.resize(sz(pts));
    for(int l = 0; l < sz(pts);) {
      int r = l;
      while(r < sz(pts) && pts[r].first == pts[l].first)
        r++;
      //cerr << l << ' ' << r << ' ' << pts[l].first << '\n';
      for(int j = l + 1; j < r; j++)
        if(pts[j].second <= buildings[pts[l].first].second)
          addedge(pts[j].ind, pts[j - 1].ind, pts[j].second - pts[j - 1].second);
      l = r;
    }
    
    sort(all(pts), [](auto a, auto b) { return pii{a.second, a.first} < pii{b.second, b.first}; });
    for(int l = 0; l < sz(pts);) {
      int r = l;
      while(r < sz(pts) && pts[r].second == pts[l].second)
        r++;
      auto &v = segm[pts[l].second];
      int ptr = 0;
      for(int j = l + 1; j < r; j++) {
        while(ptr < sz(v) && v[ptr].second < pts[j].first) ptr++;
        if(ptr == sz(v)) break;
        if(v[ptr].first > pts[j].first) continue;
        if(v[ptr].first <= pts[j - 1].first) {
          addedge(pts[j].ind, pts[j - 1].ind, buildings[pts[j].first].first - buildings[pts[j - 1].first].first);
        }
      }
      l = r;
    }
    
  }
  
  ll start(int S = -1, int T = -1) {
    //sort(all(pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
    for(auto [a, b, i] : pts) {
      if(b == 0) {
        if(S == -1) S = i;
        else { T = i; break; }
      }
    }
    //cerr << sz(pts) << '\n';
    vector<ll> arriv(sz(pts), inf);
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.emplace(0, S);
    arriv[S] = 0;
    while(!heap.empty()) {
      auto [c, node] = heap.top();
      heap.pop();
      if(c > arriv[node]) continue;
      for(auto [x, e] : g[node]) {
        if(e + c < arriv[x]) {
          arriv[x] = e + c;
          heap.emplace(e + c, x);
        }
      }
    }
    return arriv[T];
  }
}

namespace Beats {
  int r[nmax];
  int atr[nmax];
  int ggprev[nmax], ggnext[nmax];
  set<int> segm;
  set<int> availible;
  //#warning Gamble
  int gnext(int p) { auto it = availible.upper_bound(p); return (it == availible.end()? nmax - 1 : *it); }
  int gprev(int p) { auto it = availible.lower_bound(p); return (it == availible.begin()?  -1 : *prev(it)); }
  void split(int p, int y, bool add = 1) { // inutil? 
    //return;
    if(add)
      PointsG::add(p, y);
    if(add == 0) {
      availible.insert(p);
      if(availible.size() == 0) {
        ggprev[p] = -1;
        ggnext[p] = nmax - 1;
      }
      else {
        ggnext[p] = gnext(p);
        ggprev[p] = gprev(p);
        if(ggprev[p] != -1)
          ggnext[ggprev[p]] = p;
        ggprev[ggnext[p]] = p;
      }
      //return;
    }
    
    int pp1 = ggnext[p], pm1 = ggprev[p];
    //int pp1 = p + 1, pm1 = p - 1;
    
    auto it = segm.upper_bound(p);
    if(it != segm.begin() && !segm.empty()) {
      it = prev(it);
      int l = *it;
      //cerr << y << ": " << l << ' ' << p << ' ' << r[l] << ' ' << add << '\n';
      
      if(add && l <= p && p <= r[l])
        PointsG::add(p, atr[l]);
      if(l < p && p < r[l]) { // p nu se afla printre aia
        segm.insert(pp1);
        r[pp1] = r[l];
        r[l] = pm1;
        atr[pp1] = atr[l];
      }
      else if(l == p && p == r[l]) {
        segm.erase(p);
      }
      else if(l == p) {
        atr[pp1] = atr[l];
        segm.insert(pp1);
        r[pp1] = r[l];
        segm.erase(l);
      }
      else if(p == r[l]) r[l] = ggprev[r[l]];
    }
  }
  
  void color(int l, int R, int y) {
    
    //cerr << "\t" << l << ' ' << R << ' ' << y << '\n';
    split(l, y, 1);
    split(R, y, 1);
    auto it = segm.lower_bound(l);
    while(it != segm.end() && *it <= R) {
      //cerr << '\t' << *it << ' ' << r[*it] << '\n';
      PointsG::add(*it, y);
      PointsG::add(*it, atr[*it]);
      PointsG::add(r[*it], y);
      PointsG::add(r[*it], atr[*it]);
      segm.erase(it);
      it = segm.lower_bound(l);
    }
    segm.insert(l);
    r[l] = R;
    atr[l] = y;
    return;
  }
}

set<int, greater<int>> appearances;

void initpoints() {
  for(auto y : appearances) {
    for(auto a : columns[y])
      Beats::split(a, y, 0);
    repair(segm[y]);
    for(auto [l, r] : segm[y])
      Beats::color(l, r, y);
  }
  return;
}

long long min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) {
  //cerr << s << ' ' << g << '\n';
  PointsG::pts.reserve(sz(l) * 10);
  PointsG::g.reserve(sz(l) * 10);
  PointsG::add(s, 0);
  PointsG::add(g, 0);
  
  for(int i = 0; i < sz(l); i++) {
    appearances.emplace(y[i]);
    segm[y[i]].emplace_back(l[i], r[i]);
    if(l[i] <= s && s <= r[i])
      PointsG::add(s, y[i]);
    if(l[i] <= g && g <= r[i])
      PointsG::add(g, y[i]);
  }
  buildings.reserve(sz(x));
  for(int i = 0; i < sz(x); i++) {
    appearances.emplace(h[i]);
    buildings.emplace_back(x[i], h[i]);
    columns[h[i]].emplace_back(i);
  }
  
  initpoints();
  
  PointsG::init();
  auto a = PointsG::start();
  if(a == inf) return -1;
  return a;
}
#undef int

/**
      Vom spune că toamna a venit... foarte trist -
-- George Bacovia, Scântei galbene
*/

Compilation message (stderr)

walk.cpp: In function 'll PointsG::start(int, int)':
walk.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [a, b, i] : pts) {
      |              ^
walk.cpp:109:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |       auto [c, node] = heap.top();
      |            ^
walk.cpp:112:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |       for(auto [x, e] : g[node]) {
      |                ^
walk.cpp: In function 'void initpoints()':
walk.cpp:211:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  211 |     for(auto [l, r] : segm[y])
      |              ^

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