Submission #1080559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080559		veehz	Abduction 2 (JOI17_abduction2)	C++17	44 / 100	906 ms	30564 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back

/* Segment Tree */
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
  /* S op(S a, S b) {} -> Combine values */
  /* S e() {} -> Initial value (0) */
  int _n;
  vector<S> d;
  segtree() {}
  explicit segtree(int n) : segtree(vector<S>(n, e())) {}
  explicit segtree(vector<S> v) : _n(int(v.size())) {
    d.assign(4 * _n, e());
    build(v);
  }
  void build(const vector<S>& a, int v = 1, int tl = 0, int tr = -1) {
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = a[tl];
    } else {
      int tm = (tl + tr) / 2;
      build(a, v * 2, tl, tm);
      build(a, v * 2 + 1, tm + 1, tr);
      d[v] = op(d[v * 2], d[v * 2 + 1]);
    }
  }
  void set(int pos, S new_val, int tl = 0, int tr = -1, int v = 1) {
    assert(0 <= pos && pos < _n);
    if (tr == -1) tr = _n - 1;
    if (tl == tr) {
      d[v] = new_val;
    } else {
      int tm = (tl + tr) / 2;
      if (pos <= tm)
        set(pos, new_val, tl, tm, v * 2);
      else
        set(pos, new_val, tm + 1, tr, v * 2 + 1);
      d[v] = op(d[2 * v], d[2 * v + 1]);
    }
  }
  S prod(int l, int r, int tl = 0, int tr = -1, int v = 1) const {
    if (tr == -1) tr = _n - 1;
    if (r < l) return e();
    if (l == tl && r == tr) return d[v];
    int tm = (tl + tr) / 2;
    return op(prod(l, min(r, tm), tl, tm, 2 * v),
              prod(max(l, tm + 1), r, tm + 1, tr, 2 * v + 1));
  }
  // MODIFIED

  // we know op is min
  // find first element in (from, n) that is < x
  int find_next(S x, int from) {
    if(from == _n - 1) return -1;
    if (prod(from + 1, _n - 1) >= x) return -1;
    int L = from + 1, R = _n - 1;
    while (L < R) {
      int M = (L + R) / 2;
      if (prod(from + 1, M) < x)
        R = M;
      else
        L = M + 1;
    }
    // cout << "find_next(" << x << ", " << from << ") = " << L << endl;
    return L;
  }

  int find_prev(S x, int from) {
    if(from == 0) return -1;
    if (prod(0, from - 1) >= x) return -1;
    int L = 0, R = from - 1;
    while (L < R) {
      int M = (L + R + 1) / 2;
      if (prod(M, from - 1) < x)
        L = M;
      else
        R = M - 1;
    }
    // cout << "find_prev(" << x << ", " << from << ") = " << L << endl;
    return L;
  }
};
/* End: Segment Tree */

int h, w, q;
vector<int> a, b;

int op(int a, int b) { return min(a, b); }

int e() { return 1e9; }
/*
    1  4   5
3
2   v      <
6   v      ^


*/
segtree<int, op, e> sega, segb;

map<tuple<int, int, int>, int> memo;
int _dp(int x, int y, int dir);
int dp(int x, int y, int dir) {
    // cout << "call dp(" << x << ", " << y << ", " << dir << ")" << endl;
    int val = _dp(x, y, dir);
    // cout << "dp(" << x << ", " << y << ", " << dir << ") = " << val << endl;
    return val;
}
int _dp(int x, int y, int dir) {
  if (memo.count({x, y, dir})) return memo[{x, y, dir}];
  if (dir <= 1) {
    // UP/DOWN
    int cur = b[y];
    int pos = dir == 0 ? sega.find_prev(cur, x) : sega.find_next(cur, x);
    if (pos == -1) return memo[{x, y, dir}] = dir == 0 ? x : h - x - 1;
    return memo[{x, y, dir}] = max(dp(pos, y, 2), dp(pos, y, 3)) + abs(x - pos);
  } else {
    // LEFT/RIGHT
    int cur = a[x];
    int pos = dir == 2 ? segb.find_prev(cur, y) : segb.find_next(cur, y);
    if (pos == -1) return memo[{x, y, dir}] = dir == 2 ? y : w - y - 1;
    return memo[{x, y, dir}] = max(dp(x, pos, 0), dp(x, pos, 1)) + abs(y - pos);
  }
}

int dp(int x, int y) {
  return max({dp(x, y, 0), dp(x, y, 1), dp(x, y, 2), dp(x, y, 3)});
}

int main() {
  cin >> h >> w >> q;
  a.resize(h);
  b.resize(w);
  for (int i = 0; i < h; i++) cin >> a[i];
  for (int i = 0; i < w; i++) cin >> b[i];

//   turn all neg
    for (int i = 0; i < h; i++) a[i] = -a[i];
    for (int i = 0; i < w; i++) b[i] = -b[i];

  sega = segtree<int, op, e>(a);
  segb = segtree<int, op, e>(b);

  while (q--) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    cout << dp(x, y) << endl;
  }
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56