Submission #1257960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257960		xardkodych	Gap (APIO16_gap)	C++20	5.40 / 100	153 ms	1228 KiB

gap

// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;

void MinMax(long long s, long long t, long long *mn, long long *mx);
const int INF = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

class solver {
public:
  int Rand(int l, int r) {
    return l + rnd() % (r - l + 1);
  }
  pii query(int a, int b) {
    if (a > b)
      return {-1, -1};
    int u, v;
    MinMax(a, b, &u, &v);
    return {u, v};
  }
  int answer;
  int f(int l, int r) {
    if (l > r)
      return 0;
    if (auto [u,v]=query(l,r); u == v || u == -1)
      return 0;
    int mid = Rand(l, r);
    int res = 0;
    res = max(res, f(l, mid));
    res = max(res, f(mid+1, r));
    int left = query(l, mid).S;
    int right = query(mid+1, r).F;
    if (left != -1 && right != -1) {
      res = max(res, right - left);
    }
    return res;
  }
  solver(int t, int n) {
    answer = f(0, INF);
  }
};

int findGap(int32_t t, int32_t n) {
  solver sol(t, n);
  return sol.answer;
}

#undef int

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