Submission #551213

#	Time	Username	Problem	Language	Result	Execution time	Memory
551213		Sohsoh84	Rice Hub (IOI11_ricehub)	C++17	51 / 100	47 ms	3340 KiB

ricehub

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X			first
#define Y			second
#define debug(x)		cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

inline pll operator+ (const pll& a, const pll& b) {
	return {a.X + b.X, a.Y + b.Y};
}

int n;
vector<ll> vec;

namespace median {
	pll fen[MAXN], tot = {0, 0};

	inline void update(int ind, pll val) {
		tot = tot + val;
		for (++ind; ind < MAXN; ind += ind & -ind)
			fen[ind] = fen[ind] + val;
	}

	inline pll query(int ind) {
		pll ans = {0, 0};
		for (++ind; ind > 0; ind -= ind & -ind)
			ans = ans + fen[ind];
		return ans;
	}

	inline ll median() {
		int l = 0, r = int(vec.size()) - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (query(mid).Y <= (tot.Y + 1) / 2) l = mid + 1;
			else r = mid;
		}

		return l;
	}

	inline ll cost() {
		int ind = median();
		ll ans = 0;

		pll e = query(ind);
		ans += e.Y * vec[ind] - e.X;

		e = tot + pll(-e.X, -e.Y);
		ans += e.X - e.Y * vec[ind];
		return ans;
	}
}	

int besthub(int R, int L, int X[], long long B) {	
	n = R;
	for (int i = 0; i < n; i++)
		vec.push_back(X[i]);

	int ans = 0, l = 0;
	for (int r = 0; r < n; r++) {
		median::update(r, {vec[r], 1});
		while (median::cost() > B) {
			median::update(l, {-vec[l], -1});
			l++;
		}

		ans = max(ans, r - l + 1);
	}

	return ans;
}

• Subtask 1: 0 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32