Submission #236768

#	Time	Username	Problem	Language	Result	Execution time	Memory
236768		srvlt	Rice Hub (IOI11_ricehub)	C++14	100 / 100	41 ms	2688 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <ll> vll;

typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int max_N = 100003;
const ll INF = 1e18;
int n, x[max_N];

struct Set {
	deque <int> d;
	ll s = 0;
	void pb(int x) {
		d.pb(x);
		s += x;
	}
	void push_front(int x) {
		d.push_front(x);
		s += x;
	}
	int pop_front() {
		int x = d.front();
		s -= x;
		d.pop_front();
		return x;
	}
	ll sz() {
		return d.size();
	}
	void clear() {
		d.clear();
		s = 0;
	}
};

Set F, S;

void add(int x) {
	S.pb(x);
	if (F.sz() - S.sz() < 1) {
		F.pb(S.pop_front());
	}
}

void pop() {
	F.pop_front();
	if (F.sz() - S.sz() < 1) {
		F.pb(S.pop_front());
	}
}

ll get() {
	ll val = F.d.back();
	return (F.sz() * val - F.s) + (S.s - S.sz() * val);
}

ll f(int num) {
	F.clear(), S.clear();
	ll res = INF;
	for (int i = 1; i <= n; i++) {
		add(x[i]);
		if (i > num) {
			pop();
		}
		if (i >= num) {
			res = min(res, get());
		}
	}
	return res;
}

int besthub(int R, int L, int X[], ll B) {
	n = R;
	for (int i = 0; i < n; i++) {
		x[i + 1] = X[i];
	}
	int l = 1, r = R + 1;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (f(mid) <= B) {
			l = mid;
		}	else {
			r = mid;
		}
	}
	return l;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

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