Submission #1263902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263902		julia_08	Gap (APIO16_gap)	C++20	19.72 / 100	32 ms	1200 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;

ll a[MAXN];

ll ans;

int n;

void compute(ll l, ll r){

  if(r - l <= ans) return;

  if(l == -1) return;

  if(l == r){
    ans = max(ans, r - l);
    return;
  }

  ll n_l1, n_r1, n_l2, n_r2;


  if(r - l == 2){

    MinMax(l + 1, r - 1, &n_l1, &n_r1);

    if(n_l1 != -1){
      ans = max({ans, r - n_l1, n_l1 - l});

    } else ans = max(ans, r - l);

    return;

  }

  ll m = (l + r) / 2;

  MinMax(l + 1, m, &n_l1, &n_r1);

  MinMax(m + 1, r - 1, &n_l2, &n_r2);

  if(n_l1 == -1 && n_l2 == -1){
    ans = max(ans, r - l);

  } else if(n_l1 == -1){
    ans = max({ans, n_l2 - l, r - n_r2});

  } else if(n_l2 == -1){
    ans = max({ans, r - n_r1, n_l1 - l});

  } else ans = max({ans, r - n_r2, n_l2 - n_r1, n_l1 - l});

  compute(n_l1, n_r1);
  compute(n_l2, n_r2);

}

ll findGap(int t, int n){
  
  ll cur_s = 0, cur_t = 1e18;

  ll mn, mx;

  MinMax(cur_s, cur_t, &mn, &mx);

  ans = 0;
    
  compute(mn, mx);

  return ans;

}

• Subtask 1: 0 / 30
• Subtask 2: 19.7181 / 70