Submission #1193213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193213		emad234	Gap (APIO16_gap)	C++20	100 / 100	33 ms	2320 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;

long long findGap(int T, int N)
{
	ll l,r;
	MinMax(0,1e18,&l,&r);
	if(r - l + 1 == N) return 1;
	if(T == 1){
		vector<ll>v;
		v.push_back(l);
		v.push_back(r);
		l++;
		r--;
		N -= 2;
		while(N > 0){
			MinMax(l,r,&l,&r);
			if(l == -1 || r == -1) break;
			v.push_back(l);
			v.push_back(r);
			l++;
			r--;
			N -= 2;
		}
		sort(v.begin(),v.end());
		ll bg = v[0];
		ll ans = 0;
		for(auto x : v){
			ans = max(ans,x - bg);
			bg = x;
		}
		return ans;
	}
	 ll buck = (r - l + 1) / N;
	 buck += (((r - l + 1) % N) != 0);
	 ll prvT = -1;
	 ll ans = buck;
	 if(N >= 3) buck *= 2;
	 else{
		 return r - l;
	 }
	for(ll i = l; i <= r;i += buck){
		ll s = i,t = min(r, i + buck - 1);
		ll mx,mn;
		MinMax(s,t,&mn,&mx);
		// cout<<s<<' '<<t<<' '<<mx<<' '<<mn<<'\n';
		if(prvT != -1 && mn != -1) ans = max(ans, mn - prvT);
		if(mx != -1) prvT = mx;
	}
	return ans;
}

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