Submission #1080580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080580		veehz	Abduction 2 (JOI17_abduction2)	C++17	44 / 100	234 ms	35152 KiB

abduction2

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

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

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

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

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

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

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

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

map<tuple<int, int, int>, ll> memo;
ll _dp(int x, int y, int dir);
ll 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;
}
ll _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 ? 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
    int cur = a[x];
    int 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(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];
    sta[0][i] = a[i];
  }
  for (int i = 0; i < w; i++) {
    cin >> b[i];
    stb[0][i] = b[i];
  }

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

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

  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