Submission #882382

#	Time	Username	Problem	Language	Result	Execution time	Memory
882382		dubabuba	Gap (APIO16_gap)	C++14	0 / 100	15 ms	5700 KiB

gap

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second

struct node {
	node *LC, *RC;
	ll tl, tr;
	ll mn, mx;
	ll ans;

	node(ll l, ll r) {
		ans = -1;
		tl = l, tr = r;
		MinMax(l, r, &mn, &mx);
	}

	bool birth() {
		if(tl == tr) return 0;
		if(mn == mx) return 0;
		LC = new node(tl, (tl + tr) / 2);
		RC = new node((tl + tr) / 2 + 1, tr);
		return 1;
	}

	void build() {
		if(tl == tr) return;
		if(mn == mx) return;

		LC-> build();
		RC-> build();

		ans = max(LC-> ans, RC-> ans);
		if(LC-> mx != -1 && RC-> mn != -1)
			ans = max(ans, RC-> mn - LC-> mx);
	}
};

ll findGap(int T, int N) {
	const ll mxn = (ll)1e18 + 10;
	node *root = new node(0LL, mxn);
	root-> build();
	return root-> ans;
}

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