Submission #24371

#	Time	Username	Problem	Language	Result	Execution time	Memory
24371		jiaqiyang	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	2566 ms	266808 KiB

abduction2

#include <cstdio>
#include <cstring>
#include <map>
#include <tuple>

typedef long long i64;

const int N = 50000 + 10;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int n, m, a[N], b[N];
int f[4][20][N];

int init() {
  int q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
  memset(f, 0x3f, sizeof f);
  for (int i = 1; i <= n; ++i) f[0][0][i] = f[2][0][i] = a[i];
  for (int i = 1; i <= m; ++i) f[1][0][i] = f[3][0][i] = b[i];
  for (int i = 1; i < 20; ++i) {
    for (int j = (1 << (i - 1)); j <= n; ++j) f[0][i][j] = std::max(f[0][i - 1][j], f[0][i - 1][j - (1 << (i - 1))]);
    for (int j = (1 << (i - 1)); j <= m; ++j) f[3][i][j] = std::max(f[3][i - 1][j], f[3][i - 1][j - (1 << (i - 1))]);
    for (int j = m - (1 << (i - 1)); j > 0; --j) f[1][i][j] = std::max(f[1][i - 1][j], f[1][i - 1][j + (1 << (i - 1))]);
    for (int j = n - (1 << (i - 1)); j > 0; --j) f[2][i][j] = std::max(f[2][i - 1][j], f[2][i - 1][j + (1 << (i - 1))]);
  }
  return q;
}

std::map<std::tuple<int, int, int>, i64> mem;

i64 dfs(int x, int y, int k) {
  x += dx[k], y += dy[k];
  if (!(0 < x && x <= n && 0 < y && y <= m)) return 0;
  i64 &res = mem[std::make_tuple(x, y, k)];
  if (res) return res;
  if (k & 1) {
    int cur = a[x];
    for (int i = 19; i >= 0; --i) if (f[k][i][y] && f[k][i][y] <= cur) y += dy[k] << i, res += 1 << i;
    if (0 < y && y <= m) res += std::max(dfs(x, y, 0), dfs(x, y, 2)) + 1;
  } else {
    int cur = b[y];
    for (int i = 19; i >= 0; --i) if (f[k][i][x] && f[k][i][x] <= cur) x += dx[k] << i, res += 1 << i;
    if (0 < x && x <= n) res += std::max(dfs(x, y, 1), dfs(x, y, 3)) + 1;
  }
  return res;
}

int main() {
  for (int q = init(); q--;) {
    int x, y;
    scanf("%d%d", &x, &y);
    i64 ans = dfs(x, y, 0);
    for (int i = 1; i < 4; ++i) ans = std::max(ans, dfs(x, y, i));
    printf("%lld\n", ans);
  }
  return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int init()':
abduction2.cpp:16:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &q);
                              ^
abduction2.cpp:17:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                  ^
abduction2.cpp:18:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
                                                  ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:53:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
                          ^

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