Submission #794169

#	Time	Username	Problem	Language	Result	Execution time	Memory
794169		NothingXD	Meetings (IOI18_meetings)	C++17	0 / 100	11 ms	3856 KiB

meetings

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;
const int lg = 20;

int n, q;
ll h[maxn], mx[lg][maxn];
vector<int> idx;

ll getmx(int l, int r){
	r++;
	int x = 31 - __builtin_clz(r-l);
	//debug(l, r, x);
	return max(mx[l][x], mx[r-(1<<x)][x]);
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	n = H.size();
	q = L.size();
	idx.push_back(-1);
	for (int i = 0; i < n; i++){
		h[i] = H[i];
		if (h[i] == 2) idx.push_back(i);
	}
	idx.push_back(n);
	for (int i = 0; i < n; i++){
		int r = lower_bound(all(idx), i) - idx.begin();
		int l = upper_bound(all(idx), i) - idx.begin() - 1;
		mx[0][i] = max(0, idx[r] - idx[l] - 1);
		//debug(i, mx[0][i]);
	}
	for (int i = 1; i < lg; i++){
		for (int j = 0; j + (1 << i) <= n; j++){
			mx[i][j] = max(mx[i-1][j], mx[i-1][j+(1<<(i-1))]);
			//debug(i, j, mx[i][j]);
		}
	}

	vector<ll> res;

	for (int i = 0; i < q; i++){
		int l = lower_bound(all(idx), L[i]) - idx.begin();
		int r = upper_bound(all(idx), R[i]) - idx.begin() - 1;
		if (r < l){
			res.push_back(R[i]-L[i]+1);
			continue;
		}
		assert(idx[l] >= L[i] && idx[r] <= R[i]);
		//debug(L[i], R[i], idx[l], idx[r]);
		int bst = max({(ll)idx[l] - L[i], (ll)R[i] - idx[r], getmx(idx[l], idx[r])});
		res.push_back((R[i]-L[i]+1)*2-bst);
	}
	return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40