Submission #288285

#	Time	Username	Problem	Language	Result	Execution time	Memory
288285		rama_pang	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	656 ms	5372 KiB

abduction2

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

// Speed up looking next line change with sparse table,
// and memoize based on [left_end, right_end] of each
// street. State is O(H + W), since for every line x and
// the section we enter it, and from that line we go left
// or right to change to another line y and z, then if we 
// change the path and instead goes through a line that passes
// through y and z, we will never stop at x. Thus for each
// line only one "region" matters.
// Time: O(Q * (H + W))

using lint = long long;
const int MAXN = 100005;

int H, W, Q;
array<int, 3> A[MAXN];

int st[MAXN];
int et[MAXN];
lint dpl[MAXN];
lint dpr[MAXN];
int revpos[MAXN][2];

lint Solve(int X, int Y, int mask) {
  lint res = 0;
  int xl = 0, xr = H - 1;
  int yl = 0, yr = W - 1;
  memset(dpl, 0, sizeof(dpl));
  memset(dpr, 0, sizeof(dpr));
  for (int i = 0; i < H + W; i++) {
    if (A[i][2] == 0) {
      st[i] = yl, et[i] = yr;
      if (revpos[st[i]][A[i][2] ^ 1] < i) {
        int p = revpos[st[i]][A[i][2] ^ 1];
        dpl[i] = max(dpl[p] + abs(st[p] - A[i][1]), dpr[p] + abs(et[p] - A[i][1]));
      }
      if (revpos[et[i]][A[i][2] ^ 1] < i) {
        int p = revpos[et[i]][A[i][2] ^ 1];
        dpr[i] = max(dpl[p] + abs(st[p] - A[i][1]), dpr[p] + abs(et[p] - A[i][1]));
      }
      if (A[i][1] + !!(mask & 1) <= X) {
        xl = max(xl, A[i][1]);
      } else {
        xr = min(xr, A[i][1]);
      }
    } else if (A[i][2] == 1) {
      st[i] = xl, et[i] = xr;
      if (revpos[st[i]][A[i][2] ^ 1] < i) {
        int p = revpos[st[i]][A[i][2] ^ 1];
        dpl[i] = max(dpl[p] + abs(st[p] - A[i][1]), dpr[p] + abs(et[p] - A[i][1]));
      }
      if (revpos[et[i]][A[i][2] ^ 1] < i) {
        int p = revpos[et[i]][A[i][2] ^ 1];
        dpr[i] = max(dpl[p] + abs(st[p] - A[i][1]), dpr[p] + abs(et[p] - A[i][1]));
      }
      if (A[i][1] + !!(mask & 2) <= Y) {
        yl = max(yl, A[i][1]);
      } else {
        yr = min(yr, A[i][1]);
      }
    }
    if (A[i][1] == X && A[i][2] == 0) {
      res = max(res, dpl[i] + abs(Y - st[i]));
      res = max(res, dpr[i] + abs(Y - et[i]));
    }
    if (A[i][1] == Y && A[i][2] == 1) {
      res = max(res, dpl[i] + abs(X - st[i]));
      res = max(res, dpr[i] + abs(X - et[i]));
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> H >> W >> Q;
  for (int i = 0; i < H; i++) {
    cin >> A[i][0];
    A[i][1] = i;
    A[i][2] = 0;
  }
  for (int i = 0; i < W; i++) {
    cin >> A[i + H][0];
    A[i + H][1] = i;
    A[i + H][2] = 1;
  }
  sort(begin(A), end(A));
  reverse(begin(A), end(A));
  for (int i = 0; i < H + W; i++) {
    revpos[A[i][1]][A[i][2]] = i;
  }
  for (int i = 0; i < Q; i++) {
    int S, T;
    cin >> S >> T;
    S--, T--;
    cout << max({Solve(S, T, 0), Solve(S, T, 1), 
                 Solve(S, T, 2), Solve(S, T, 3)}) << '\n';
  }
  return 0;
}

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