Submission #1025880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025880		TraianDanciu	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	746 ms	132692 KiB

abduction2

#include <stdio.h>
#include <map>

static inline long long min(long long a, long long b) {
  return a < b ? a : b;
}
static inline long long max(long long a, long long b) {
  return a > b ? a : b;
}

#define MAXN 50000
#define LOGN 16
#define VERTICAL 0
#define ORIZONTAL 1

int n, m, a[LOGN][MAXN], b[LOGN][MAXN], lg2[MAXN + 1];
std::map<long long, long long> memo;

long long solve(int l, int c, int stare) {
  int i, sus, jos, st, dr;
  long long ans;
  
  if(l < 0 || c < 0 || l >= n || c >= m) {
    return -1;
  }
  
  if(memo.count((1LL * l * m + c) * 2 + stare)) {
    return memo[(1LL * l * m + c) * 2 + stare];
  }
  
  ans = 0;
  if(stare == VERTICAL) {
    sus = l - 1;
    jos = l + 1;
    for(i = LOGN - 1; i >= 0; i--) {
      if(sus - (1 << i) + 1 >= 0 && a[i][sus - (1 << i) + 1]
                                                        <= b[0][c]) {
        sus -= 1 << i;
      }
      if(jos + (1 << i) - 1 < n && a[i][jos] <= b[0][c]) {
        jos += 1 << i;
      }
    }
    
    ans = max(ans, solve(sus, c, ORIZONTAL) + l - sus);
    ans = max(ans, solve(jos, c, ORIZONTAL) + jos - l);
  } else {
    st = c - 1;
    dr = c + 1;
    for(i = LOGN - 1; i >= 0; i--) {
      if(st - (1 << i) + 1 >= 0 && b[i][st - (1 << i) + 1]
                                                        <= a[0][l]) {
        st -= 1 << i;
      }
      if(dr + (1 << i) - 1 < m && b[i][dr] <= a[0][l]) {
        dr += 1 << i;
      }
    }
    
    ans = max(ans, solve(l, st, VERTICAL) + c - st);
    ans = max(ans, solve(l, dr, VERTICAL) + dr - c);
  }
  
  return memo[(1LL * l * m + c) * 2 + stare] = ans;
}

int main() {
  int q, i, j;
  
  scanf("%d%d%d", &n, &m, &q);
  for(i = 0; i < n; i++) {
    scanf("%d", &a[0][i]);
  }
  for(i = 0; i < m; i++) {
    scanf("%d", &b[0][i]);
  }
  
  for(i = 2; i <= MAXN; i++) {
    lg2[i] = 1 + lg2[i >> 1];
  } 
  
  for(i = 1; i <= lg2[n]; i++) {
    for(j = 0; j + (1 << i) <= n; j++) {
      a[i][j] = max(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
    }
  }
  
  for(i = 1; i <= lg2[m]; i++) {
    for(j = 0; j + (1 << i) <= m; j++) {
      b[i][j] = max(b[i - 1][j], b[i - 1][j + (1 << (i - 1))]);
    }
  }
  
  while(q--) {
    scanf("%d%d", &i, &j);
    i--;
    j--;
    printf("%lld\n", max(solve(i, j, VERTICAL),
                         solve(i, j, ORIZONTAL)));
  }
  
  return 0;
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d%d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &a[0][i]);
      |     ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d", &b[0][i]);
      |     ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d%d", &i, &j);
      |     ~~~~~^~~~~~~~~~~~~~~~

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