제출 #101836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101836		cerberus	Gap (APIO16_gap)	C++17	100 / 100	65 ms	1448 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>

#ifndef LOCAL
#include "gap.h"
#endif

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);
ll findGap_small(int N);
void query(ll s, ll t, ll &mn, ll &mx, int T);

int M;
set<pll> S;

#ifdef LOCAL
int main() {
	int T, n; cin >> T >> 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(T, n) << endl << M << ' ';
	if (T == 1) {
		cout << (n + 1) / 2 << endl;
	} else {
		cout << 3 * n << endl;
	}
}
#endif

ll findGap(int T, int N) {
	if (T == 1) {
		return findGap_small(N);
	}

	ll mn, mx;
	query(0, INF, mn, mx, T);
	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, T);
			mx = B;
			if (mn == -1) {
				mn = B;
			}
		} else {
			query(A + 1, A + sz, mn, mx, T);
		}
		if (mn == -1) {
			sz *= 2;
			continue;
		}
		best = max(best, mn - A);
		sz = best + 1;
		A = mx;
	}
	return best;
}

ll findGap_small(int N) {
	ll mn, mx;
	query(0, INF, mn, mx, 1);
	ll best = 0;
	ll A = mn, B = mx;
	N -= 2;
	while (A < B and N > 0) {
		query(A + 1, B - 1, mn, mx, 1);
		if (mn == -1) {
			best = max(best, B - A);
			break;
		} else {
			best = max(best, mn - A);
			best = max(best, B - mx);
			A = mn; B = mx;
			N -= 2;
		}
	}
	return max(best, B - A);
}

void query(ll s, ll t, ll &mn, ll &mx, int T) {
	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;
		if (T == 2) {
			M += (r->second - l->second + 1);
		}
	} else {
		mn = mx = -1;
	}
#else
	MinMax(s, t, &mn, &mx);
#endif
}

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