Submission #1080582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080582		veehz	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	2054 ms	326228 KiB

abduction2

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

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

const ll MAXN = 50001;
const ll K = 16;
ll sta[K + 1][MAXN];
ll stb[K + 1][MAXN];
// vector<vector<ll>> sta(K + 1, vector<ll>(MAXN)),
//     stb(K + 1, vector<ll>(MAXN));

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

ll log2_floor(unsigned long long i) {
  return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}

ll max(ll st[K + 1][MAXN], ll l, ll r) {
// ll max(vector<vector<ll>> &st, ll l, ll r) {
  ll j = log2_floor(r - l + 1);
  return max(st[j][l], st[j][r - (1 << j) + 1]);
}

ll find_next(ll st[K + 1][MAXN], ll x, ll l, ll r) {
// ll find_next(vector<vector<ll>> &st, ll x, ll l, ll r) {
  if (l > r) return -1;
  if (max(st, l, r) < x) return -1;
  ll L = l, R = r;
  while (L < R) {
    ll M = (L + R) / 2;
    if (max(st, l, M) < x) {
      L = M + 1;
    } else {
      R = M;
    }
  }
  return L;
}

ll find_prev(ll st[K + 1][MAXN], ll x, ll l, ll r) {
// ll find_prev(vector<vector<ll>> &st, ll x, ll l, ll r) {
  if (l > r) return -1;
  if (max(st, l, r) < x) return -1;
  ll L = l, R = r;
  while (L < R) {
    ll M = (L + R + 1) / 2;
    if (max(st, M, r) < x) {
      R = M - 1;
    } else {
      L = M;
    }
  }
  return L;
}

map<tuple<ll, ll, ll>, ll> memo;
ll _dp(ll x, ll y, ll dir);
ll dp(ll x, ll y, ll dir) {
  // cout << "call dp(" << x << ", " << y << ", " << dir << ")" << endl;
  ll val = _dp(x, y, dir);
  // cout << "dp(" << x << ", " << y << ", " << dir << ") = " << val << endl;
  return val;
}
ll _dp(ll x, ll y, ll dir) {
  if (memo.count({x, y, dir})) return memo[{x, y, dir}];
  if (dir <= 1) {
    // UP/DOWN
    ll cur = b[y];
    ll pos = dir == 0 ? find_prev(sta, cur, 0, x - 1)
                       : find_next(sta, cur, x + 1, h - 1);
    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
    ll cur = a[x];
    ll pos = dir == 2 ? find_prev(stb, cur, 0, y - 1)
                       : find_next(stb, cur, y + 1, w - 1);
    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);
  }
}

ll dp(ll x, ll 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 (ll i = 0; i < h; i++) {
    cin >> a[i];
    sta[0][i] = a[i];
  }
  for (ll i = 0; i < w; i++) {
    cin >> b[i];
    stb[0][i] = b[i];
  }

  //   for (ll i = 0; i < h; i++) {
  //     cin >> sta[0][i];
  //   }
  //   for (ll i = 0; i < w; i++) {
  //     cin >> stb[0][i];
  //   }

  for (ll i = 1; i <= K; i++) {
    for (ll j = 0; j + (1 << i) <= h; j++) {
      sta[i][j] = max(sta[i - 1][j], sta[i - 1][j + (1 << (i - 1))]);
    }
    for (ll j = 0; j + (1 << i) <= w; j++) {
      stb[i][j] = max(stb[i - 1][j], stb[i - 1][j + (1 << (i - 1))]);
    }
  }

  while (q--) {
    ll 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: 56 / 56