2019牛客暑假多校第一场A

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, a[100005], b[100005];
int bin[25], dp1[25][100005], dp2[25][100005], Log[100005], val[100005];

int get_max_num1(int x, int y){
  return a[x] >= a[y] ? y : x;
}

int get_max_num2(int x, int y){
  return b[x] >= b[y] ? y : x;
}

bool fun(int L, int R){
  if(L >= R) return true;
  int t = Log[R - L + 1];
  int p1 = get_max_num1(dp1[t][L], dp1[t][R - bin[t] + 1]);
  int p2 = get_max_num2(dp2[t][L], dp2[t][R - bin[t] + 1]);
  if(p1 == p2){
    if(!fun(L, p1 - 1)) return false;
    if(!fun(p1 + 1, R)) return false;
    return true;
  }else return false;
}

int main()
{
  //freopen("in.txt", "r", stdin);
  //freopen("out.txt", "w", stdout);

  bin[0] = 1;
  for (int i = 1; i <= 20; i++) bin[i] = bin[i - 1] * 2;
  Log[0] = -1;
  for (int i = 1; i <= 100000; i++) Log[i] = Log[i / 2] + 1;
  while(scanf("%d", &n) == 1){
      for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        dp1[0][i] = i;
      }
      for (int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
        dp2[0][i] = i;
      }
      for (int i = 1; i <= Log[n]; i++){
        for (int j = 1; j <= n; j++){
          if(j + bin[i] - 1 <= n){
            dp1[i][j] = get_max_num1(dp1[i - 1][j], dp1[i - 1][j + bin[i - 1]]);
            dp2[i][j] = get_max_num2(dp2[i - 1][j], dp2[i - 1][j + bin[i - 1]]);
          }
      }
    }
    int l = 1, r = n, ans = 1;
    while(l <= r){
      int mid = (l + r) >> 1;
      if(fun(1, mid)) l = mid + 1, ans = mid;
      else r = mid - 1;
    }
    printf("%d\n", ans);
  }

  return 0;
}
/**/