Submission #883222

#	Time	Username	Problem	Language	Result	Execution time	Memory
883222		MilosMilutinovic	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	4237 ms	31344 KiB

abduction2

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

const int MAX = 50005;
const int L = 18;

int h, w, q, a[MAX], b[MAX], logs[MAX];
int maxa[MAX][L], maxb[MAX][L];

unordered_map<int, bool> was[4];
unordered_map<int, long long> dp[4];

int MaxA(int L, int R) {
  int k = logs[R - L + 1];
  return max(maxa[L][k], maxa[R - (1 << k) + 1][k]);
}

int MaxB(int L, int R) {
  int k = logs[R - L + 1];
  return max(maxb[L][k], maxb[R - (1 << k) + 1][k]);
}

pair<int, int> Go(int x, int y, int dir) {
  if (dir == 0) {
    // up
    if (x == 0) {
      return make_pair(x, y);
    }
    x--;
    {
      if (MaxA(0, x) < b[y]) {
        return make_pair(0, y);
      }
      int low = 0, high = x, pos = x;
      while (low <= high) {
        int mid = low + high >> 1;
        if (MaxA(mid, x) >= b[y]) {
          pos = mid;
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      return make_pair(pos, y);
    }
    /* while (x > 0 && a[x] < b[y]) {
      x -= 1;
    }
    return make_pair(x, y); */
  }
  if (dir == 1) {
    // down
    if (x == h - 1) {
      return make_pair(x, y);
    }
    x += 1;
    {
      if (MaxA(x, h - 1) < b[y]) {
        return make_pair(h - 1, y);
      }
      int low = x, high = h - 1, pos = h - 1;
      while (low <= high) {
        int mid = low + high >> 1;
        if (MaxA(x, mid) >= b[y]) {
          pos = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      return make_pair(pos, y);
    } 
    /* while (x + 1 < h && a[x] < b[y]) {
      x += 1;
    }
    return make_pair(x, y); */
  }
  if (dir == 2) {
    // left
    if (y == 0) {
      return make_pair(x, y);
    }
    y -= 1;
    {
      if (MaxB(0, y) < a[x]) {
        return make_pair(x, 0);
      }
      int low = 0, high = y, pos = y;
      while (low <= high) {
        int mid = low + high >> 1;
        if (MaxB(mid, y) >= a[x]) {
          pos = mid;
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      return make_pair(x, pos);
    } 
    /* while (y > 0 && a[x] > b[y]) {
      y -= 1;
    }
    return make_pair(x, y); */
  }
  if (dir == 3) {
    // right
    if (y == w - 1) {
      return make_pair(x, y);
    }
    y += 1;
    {
      if (MaxB(y, w - 1) < a[x]) {
        return make_pair(x, w - 1);
      }
      int low = y, high = w - 1, pos = y;
      while (low <= high) {
        int mid = low + high >> 1;
        if (MaxB(y, mid) >= a[x]) {
          pos = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      return make_pair(x, pos);
    } 
    /* while (y + 1 < w && a[x] > b[y]) {
      y += 1;
    }
    return make_pair(x, y); */
  }
  assert(false);
  return make_pair(-1, -1);
}

long long Solve(int x, int y, int dir) {
  if (dir <= 1) {
    if (a[x] < b[y]) {
      return 0LL;
    }
  } else {
    if (a[x] > b[y]) {
      return 0LL;
    }
  }
  int curr = x * w + y;
  if (was[dir][curr]) {
    return dp[dir][curr];
  }
  was[dir][curr] = true;
  if (dir == 0 || dir == 1) {
    {
      pair<int, int> nxt = Go(x, y, 2);
      if (nxt.first != x || nxt.second != y) {
        dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 2) + abs(nxt.first - x) + abs(nxt.second - y));
      }
    }
    {
      pair<int, int> nxt = Go(x, y, 3);
      if (nxt.first != x || nxt.second != y) {
        dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 3) + abs(nxt.first - x) + abs(nxt.second - y));
      }
    }
  } 
  if (dir == 2 || dir == 3) {
    {
      pair<int, int> nxt = Go(x, y, 0);
      if (nxt.first != x || nxt.second != y) {
        dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 0) + abs(nxt.first - x) + abs(nxt.second - y));
      }
    }
    {
      pair<int, int> nxt = Go(x, y, 1);
      if (nxt.first != x || nxt.second != y) {
        dp[dir][curr] = max(dp[dir][curr], Solve(nxt.first, nxt.second, 1) + abs(nxt.first - x) + abs(nxt.second - y));
      }
    }
  }
  return dp[dir][curr];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //int h, w, q;
  cin >> h >> w >> q;
  //vector<int> a(h);
  for (int i = 0; i < h; i++) {
    cin >> a[i];
  }
  //vector<int> b(w);
  for (int i = 0; i < w; i++) {
    cin >> b[i];
  }
  //const int L = 20;
  //vector<vector<int>> maxa(h, vector<int>(L));
  //vector<vector<int>> maxb(w, vector<int>(L));
  for (int i = 0; i < h; i++) {
    maxa[i][0] = a[i];
  }
  for (int i = 0; i < w; i++) {
    maxb[i][0] = b[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i + (1 << j) <= h; i++) {
      maxa[i][j] = max(maxa[i][j - 1], maxa[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i + (1 << j) <= w; i++) {
      maxb[i][j] = max(maxb[i][j - 1], maxb[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 2; i <= max(h, w); i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    long long res = 1;
    for (int dir = 0; dir < 4; dir++) {
      pair<int, int> cell = Go(x, y, dir);
      int nx = cell.first;
      int ny = cell.second;
      if (nx != x || ny != y) {
        res = max(res, Solve(nx, ny, dir) + abs(x - nx) + abs(y - ny));
      }
    }
    cout << res << '\n';
    for (int dir = 0; dir < 4; dir++) {
      was[dir].clear();
      dp[dir].clear();
    }
  }
  return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'std::pair<int, int> Go(int, int, int)':
abduction2.cpp:37:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
abduction2.cpp:64:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
abduction2.cpp:91:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
abduction2.cpp:118:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~

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