Submission #373197

#	Time	Username	Problem	Language	Result	Execution time	Memory
373197		Kanon	Sky Walking (IOI19_walk)	C++14	10 / 100	1560 ms	166352 KiB

walk

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

class segtree {
  public:
  struct node {

    long long ad = 0;
    int mu = 1;
    long long sum = 0;

    void apply(int l, int r, int v) {
      if (v >= 0) {
        ad += v;
        sum += 1LL * v * (r - l + 1);
      } else {
        v = ~v;
        ad *= v;
        mu *= v;
        sum *= v;
      }
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.sum = a.sum + b.sum;
    return res;
  }

  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].mu != 1) {
      tree[x + 1].apply(l, y, ~tree[x].mu);
      tree[z].apply(y + 1, r, ~tree[x].mu);
      tree[x].mu = 1;
    }
    if (tree[x].ad != 0) {
      tree[x + 1].apply(l, y, tree[x].ad);
      tree[z].apply(y + 1, r, tree[x].ad);
      tree[x].ad = 0;
    }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T&... t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }

  template <typename M, typename... T>
  segtree(const vector<M> &v, const T&... t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  segtree(){};

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }

};

struct edge {
  int t;
  int dis;
  edge(int _t, int _dis) : t(_t), dis(_dis){};
};

vector<long long> calc(int n, int s, int t, vector<vector<edge>> g) {
  vector<long long> ret(n, LLONG_MAX);
  ret[s] = 0;
  set<pair<long long, int>> que;
  vector<int> was(n);
  que.insert({ret[s], s});
  while(que.size()) {
    int v = que.begin()->second;
    que.erase(que.begin());
    if(was[v]) continue;
    was[v] = 1;
    for(edge e : g[v]) {
      int u = e.t;
      if(ret[u] > ret[v] + e.dis) {
        ret[u] = ret[v] + e.dis;
        que.insert(make_pair(ret[u], u));
      }
    }
  }
  return ret;
}

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

long long min_distance(vector<int> px, vector<int> h, vector<int> l, vector<int> r, vector<int> py, int s, int t) {
  int n = px.size();
  int m = py.size();
  set<pair<int, int>> p;
  auto add = [&](int x, int y) {
    p.insert(make_pair(x, y));
  };
  map<int, int> bound;
  for(int i = 0; i < n; i++) bound[px[i]] = i;
  add(px[s], 0);
  add(px[t], 0);
  for(int i = 0; i < m; i++) {
    add(px[l[i]], py[i]);
    add(px[r[i]], py[i]);
  }
//
  SparseTable<int> d(h, [&](int i, int j){return max(i, j);});
  auto find_left = [&](int l, int r, int y) {
    if(d.get(l, r) < y) return -1;
    while(r - l >= 1) {
      int mid = (r + l) >> 1;
      if(d.get(l, mid) < y) l = mid + 1;
      else r = mid;
    }
    return r;
  };
  auto find_right = [&](int l, int r, int y) {
    if(d.get(l, r) < y) return -1;
    while(r - l >= 1) {
      int mid = (r + l) >> 1;
      if(d.get(mid + 1, r) < y) r = mid;
      else l = mid + 1;
    }
    return r;
  };
  //near pole
  for(int i = 0; i < m; i++) {
    int y = py[i];
    for(int rot = 0; rot < 2; rot++) {
      if(l[i] < s && s < r[i]) {
        int ll = find_right(l[i], s, y);
        int rr = find_left(s, r[i], y);
        if(ll != -1) add(px[ll], y);
        if(rr != -1) add(px[rr], y);
      }
      swap(s, t);
    }
  }

  vector<pair<int, int>> ad;
  // near ver
  {
    for(auto pp : p) {
      int x = pp.first, y = pp.second;
      int id = lower_bound(px.begin(), px.end(), x) - px.begin();
      if(id < n - 1) {
        int ll = find_left(id + 1, n - 1, y);
        if(ll != -1) ad.emplace_back(px[ll], y);
      }
      if(id > 0) {
        int rr = find_right(0, id - 1, y);
        if(rr != -1) ad.emplace_back(px[rr], y);
      }
    }
  }
  //near hor
  {
    vector<pair<int, int>> pos;
    for(auto i : p) pos.push_back(i);
    sort(pos.begin(), pos.end(), [&](pair<int, int> i, pair<int, int> j){return i.second < j.second;});
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j){return py[i] < py[j];});
    segtree st(n);

    for(int rot = 0; rot < 2; rot++) {
      int cur = 0;
      for(auto pp : pos) {
        int x = pp.first, y = pp.second;
        if(y == 0) continue;
        while(py[order[cur]] != y) {
          int id = order[cur];
          st.modify(l[id], r[id], ~0);
          st.modify(l[id], r[id], py[id]);
          cur++;
        }
        int id = bound[x];
        int yy = st.get(id, id).sum;
        if(0 < yy && yy <= h[id]) ad.emplace_back(x, yy);
      }
      reverse(pos.begin(), pos.end());
      reverse(order.begin(), order.end());
      st.modify(0, n - 1, ~0);
    }
  }
  for(auto i : ad) add(i.first, i.second);
  
  //numerate
  int sz = p.size();
  map<pair<int, int>, int> id;
  for(auto i : p) {
    int fp = id.size();
    id[i] = fp;
  }
  vector<vector<edge>> g(sz);
  // add ver edged
  int cnt = 0;
  for(auto it = p.begin(); next(it) != p.end(); it++) {
    if(it->first == next(it)->first) {
      int u = cnt;
      int v = cnt + 1;
      int dis = abs(it->second - next(it)->second);
      g[u].emplace_back(v, dis);
      g[v].emplace_back(u, dis);
    }
    cnt++;
  }
  {
    if(p.size() >= 100000) return -1;
  }
  // add hor edge
  set<pair<int, int>> rp;
  for(auto i : p) rp.insert(make_pair(i.second, i.first));
  for(int i = 0; i < m; i++) {
    int L = px[l[i]], R = px[r[i]], y = py[i];
    for(auto it = rp.lower_bound(make_pair(y, L)); it != rp.end() && next(it) != rp.end() && *next(it) <= make_pair(y, R); it++) {
      int x = it->second, y = it->first, xx = next(it)->second, yy = next(it)->first;
      int u = id[make_pair(x, y)], v = id[make_pair(xx, yy)];
      int dis = abs(x - xx) + abs(y - yy);
      g[u].emplace_back(v, dis);
      g[v].emplace_back(u, dis);
    }
  }

  //
  int ss = id[make_pair(px[s], 0)];
  int tt = id[make_pair(px[t], 0)];
  vector<long long> ret = calc(sz, ss, tt, g);
  if(ret[tt] == LLONG_MAX) return -1;
  return ret[tt];
}

/*int main() {
  cout << min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5);
  return 0;
}
*/

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