Submission #570564

#	Time	Username	Problem	Language	Result	Execution time	Memory
570564		iancu	Abduction 2 (JOI17_abduction2)	C++14	13 / 100	4 ms	340 KiB

abduction2

#include <bits/stdc++.h>
#include <cassert>

#define NORTH 0
#define SOUTH 1
#define EAST  2
#define WEST  3

using namespace std;

const int N = 5e4 + 5;

struct Node {
  int x, y;
  int val;
  int dir;
  long long dist;

  bool operator<(const Node& n) const {
    return val > n.val;
  }
};

int h, w;
int a[N], b[N];

long long solve(int x, int y, int dir) {
  vector<int> fh(h + w + 1, 0), fw(h + w + 1, 0);
  int hl, hr, wl, wr;
  long long ans = 0;
  hl = hr = x;
  wl = wr = y;
  if (dir == 0) hl = max(hl - 1, 1);
  else if (dir == 1) hr = min(hr + 1, h);
  else if (dir == 2) wr = min(wr + 1, w);
  else wl = max(wl - 1, 1);
  priority_queue<Node> pq;
  pq.push({x, y, 0, dir, 0});
  while (!pq.empty()) {
    auto n = pq.top();
    //cout << n.x << " " << n.y << " " << n.dir << " " << n.dist << endl;
    pq.pop();
    ans = max(ans, n.dist);

    if (n.dir == NORTH || n.dir == SOUTH) {
      if (fh[n.y] >= 4)
        continue;
      ++fh[n.y];
    } else {
      if (fw[n.x] >= 4)
        continue;
      ++fw[n.x];
    }

    if (n.dir == NORTH && n.x == 1)
      continue;
    if (n.dir == SOUTH && n.x == h)
      continue;
    if (n.dir == EAST  && n.y == w)
      continue;
    if (n.dir == WEST  && n.y == 1)
      continue;

    if (n.dir == NORTH) {
      while (hl > 1 && a[hl] <= b[n.y])
        --hl;
      if (a[hl] <= b[n.y]) {
        ans = max(ans, n.dist + n.x - hl);
        continue;
      }
      pq.push({hl, n.y, a[hl], WEST, n.dist + n.x - hl});
      pq.push({hl, n.y, a[hl], EAST, n.dist + n.x - hl});
    } else if (n.dir == SOUTH) {
      while (hr < h && a[hr] <= b[n.y])
        ++hr;
      if (a[hr] <= b[n.y]) {
        ans = max(ans, n.dist + hr - n.x);
        continue;
      }
      pq.push({hr, n.y, a[hr], WEST, n.dist + hr - n.x});
      pq.push({hr, n.y, a[hr], EAST, n.dist + hr - n.x});
    } else if (n.dir == EAST) {
      while (wr < w && b[wr] <= a[n.x])
        ++wr;
      if (b[wr] <= a[n.x]) {
        ans = max(ans, n.dist + wr - n.y);
        continue;
      }
      pq.push({n.x, wr, b[wr], NORTH, n.dist + wr - n.y});
      pq.push({n.x, wr, b[wr], SOUTH, n.dist + wr - n.y});
    } else {
      while (wl > 1 && b[wl] <= a[n.x])
        --wl;
      if (b[wl] <= a[n.x]) {
        ans = max(ans, n.dist + n.y - wl);
        continue;
      }
      pq.push({n.x, wl, b[wl], NORTH, n.dist + n.y - wl});
      pq.push({n.x, wl, b[wl], SOUTH, n.dist + n.y - wl});
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int q;
  cin >> h >> w >> q;
  for (int i = 1; i <= h; ++i)
    cin >> a[i];
  for (int i = 1; i <= w; ++i)
    cin >> b[i];
  while (q--) {
    int x, y;
    cin >> x >> y;
    long long ans = 0;
    for (int i = 0; i < 4; ++i)
      ans = max(ans, solve(x, y, i));
    cout << ans << "\n";
  }
  return 0;
}

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