Submission #1260589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260589		julia_08	Gap (APIO16_gap)	C++20	0 / 100	44 ms	4092 KiB

gap

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

using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;

vector<ll> compute(ll l, ll r){

  if(l == -1) return {};

  ll m = (l + r) / 2;

  ll n_l1 = -1, n_r1 = -1, n_l2 = -1, n_r2 = -1;

  if(l + 1 <= m) MinMax(l + 1, m, &n_l1, &n_r1);
  if(m + 1 <= r - 1) MinMax(m + 1, r - 1, &n_l2, &n_r2);

  vector<ll> v_l = compute(n_l1, n_r1);
  vector<ll> v_r = compute(n_l2, n_r2);

  vector<ll> res;

  res.push_back(l);

  for(auto x : v_l) res.push_back(x);
  for(auto x : v_r) res.push_back(x);

  res.push_back(r);
    
  return res;

}

ll findGap(int t, int n){
  
  int l = 1, r = n;

  ll cur_s = 0, cur_t = 1e18;

  ll mn, mx;

  MinMax(cur_s, cur_t, &mn, &mx);
  
  vector<ll> a = compute(mn, mx);

  ll ans = 0;

  for(int i=0; i<(n - 1); i++) ans = max(ans, a[i + 1] - a[i]);

  return ans;

}

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