Submission #101832

#	Time	Username	Problem	Language	Result	Execution time	Memory
101832		cerberus	Gap (APIO16_gap)	C++17	0 / 100	78 ms	3068 KiB

gap

/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

#include "gap.h"

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const ll INF = 1e18;

ll findGap(int T, int N);
void query(ll s, ll t, ll &mn, ll &mx);

int M;
set<pll> S;

#ifdef LOCAL
int main() {
	int n; cin >> n;
	vector<ll> v(n);
	for (int i = 1; i <= n; ++i) {
		cin >> v[i - 1];
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; ++i) {
		S.insert({v[i], i});
	}
	S.insert({-1, -1});
	S.insert({INF + 1, n});
	cout << findGap(1, n) << endl << M << ' ' << 3 * n << endl;
}
#endif

ll findGap(int T, int N) {
	ll mn, mx;
	query(0, INF, mn, mx);
	if (N <= 2) {
		return mx - mn;
	}

	ll A = mn, B = mx, best = (B - A + N - 2) / (N - 1), sz = best + 1;
	while (A < B) {
		if (A + sz >= B) {
			query(A + 1, B - 1, mn, mx);
			mx = B;
			if (mn == -1) {
				mn = B;
			}
		} else {
			query(A + 1, A + sz, mn, mx);
		}
		if (mn == -1) {
			sz *= 2;
			continue;
		}
		best = max(best, mn - A);
		A = mx;
	}
	return best;
}

void query(ll s, ll t, ll &mn, ll &mx) {
	if (s > t) {
		mn = mx = -1;
		return;
	}
#ifdef LOCAL
	assert(s <= t);
	++M;
	auto l = S.lower_bound({s, -INF});
	auto r = S.upper_bound({t, INF + 10});
	--r;
	if (l->second <= r->second) {
		mn = l->first;
		mx = r->first;
		M += (r->second - l->second + 1);
	} else {
		mn = mx = -1;
	}
#else
	MinMax(s, t, &mn, &mx);
#endif
}

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