Submission #882377

#	Time	Username	Problem	Language	Result	Execution time	Memory
882377		dubabuba	Gap (APIO16_gap)	C++14	0 / 100	20 ms	5668 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

bool sussy = 1;
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);
		if(mn != -1) sussy = 0;
	}

	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;
	}

	ll merge(node *L, node *R) {
		ll ret = max(L-> ans, R-> ans);
		// if(L-> mx == -1) return ret;
		// if(R-> mn == -1) return ret;
		ret = max(ret, R-> mn - L-> mx);
		return ret;
	}

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

		LC-> build();
		RC-> build();
		ans = merge(LC, RC);
	}
};

ll findGap(int T, int N) {
	const ll mxn = (ll)1e18;
	node *root = new node(1LL, mxn);
	// assert(root-> ans != -1);
	assert(sussy);
	return root-> ans;
}

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