Submission #685628

#	Time	Username	Problem	Language	Result	Execution time	Memory
685628		cadmiumsky	Sky Walking (IOI19_walk)	C++14	25 / 100	1740 ms	231008 KiB

walk

#include <bits/stdc++.h>
#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[i].second == v[i + 1].first) {
      v[last].second = v[i + 1].second;
      v[i + 1].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) {
    //cerr << x << ' ' << y << " - " << w << '\n';
    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];
      repair(v);
      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;
      }
      //cerr << a << ' ' << b << ' ' << i << '\n';
    }
    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;
    //cerr << S << ' ' << T << ' ' << pts[S].first << ' ' << pts[S].second << '\n';
    //cerr <<  pts[T].first << ' ' << pts[T].second << '\n';
    //cerr << "Mogus\n";
    //exit(0);
    //int cnt = 0;
    while(!heap.empty()) {
      //cnt++;
      //if(cnt % 10000 == 0)
        //cerr << "Mogus\n";
    
      auto [c, node] = heap.top();
      heap.pop();
      if(c > arriv[node]) continue;
      //cerr << node << ' ' << c << '\n';
      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];
  set<int> segm;
  //#warning Gamble
  void split(int p, int y, bool add = 1) { // inutil? 
    
    //return;
    if(add)
      PointsG::add(p, y);
    
    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(p + 1);
        r[p + 1] = r[l];
        r[l] = p - 1;
        atr[p + 1] = atr[l];
      }
      else if(l == p && p == r[l]) {
        segm.erase(p);
      }
      else if(l == p) {
        atr[p + 1] = atr[l];
        segm.insert(p + 1);
        r[p + 1] = r[l];
        segm.erase(l);
      }
      else if(p == r[l]) r[l]--;
    }
    if(add == 0) {
      r[p] = p;
      atr[p] = y;
      segm.insert(p);
    }
  }
  
  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;
    //cerr << "\t------\n";
    return;
  }
}

void initpoints() {
  for(auto &[y, v] : segm) {
    //for(auto a : columns[y])
      //Beats::split(a, y, 0);
    for(auto [l, r] : v)
      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) {
  
  PointsG::add(s, 0);
  PointsG::add(g, 0);
  PointsG::pts.reserve(sz(l) * 8);
  PointsG::g.reserve(sz(l) * 8);
  
  for(int i = 0; i < sz(l); 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++) {
    buildings.emplace_back(x[i], h[i]);
    columns[h[i]].emplace_back(i);
  }
  
  
  initpoints();
  
  
  //int o = 0;
  //sort(all(PointsG::pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
  //PointsG::pts.resize(distance(PointsG::pts.begin(), unique(all(PointsG::pts))));
  //cerr << PointsG::pts.size() << '\n';
  //for(auto [x, y, i] : PointsG::pts) {
    //cerr << buildings[x].first << ' ' << y << '\n';
  //}
  //return 69;
  
  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(ll, ll)':
walk.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [a, b, i] : pts) {
      |              ^
walk.cpp:120:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |       auto [c, node] = heap.top();
      |            ^
walk.cpp:124:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |       for(auto [x, e] : g[node]) {
      |                ^
walk.cpp: In function 'void initpoints()':
walk.cpp:202:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  202 |   for(auto &[y, v] : segm) {
      |             ^
walk.cpp:205:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |     for(auto [l, r] : v)
      |              ^

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