oj.uz

Submission #570553

# Submission time Handle Problem Language Result Execution time Memory
570553 2022-05-30T12:31:07 Z iancu Abduction 2 (JOI17_abduction2) C++14
13 / 100
 4340 ms 524288 KB 
#include <bits/stdc++.h>

#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 {
    if (val != n.val)
      return val > n.val;
    return dist < n.dist;
  }
};

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

long long solve(int x, int y, int dir) {
  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.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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Runtime error 4045 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Runtime error 4045 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 920 KB Output is correct
2 Correct 37 ms 604 KB Output is correct
3 Correct 51 ms 1216 KB Output is correct
4 Correct 56 ms 992 KB Output is correct
5 Correct 64 ms 1712 KB Output is correct
6 Correct 16 ms 340 KB Output is correct
7 Correct 16 ms 376 KB Output is correct
8 Runtime error 4340 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Runtime error 4045 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -