Submission #122511

#	Time	Username	Problem	Language	Result	Execution time	Memory
122511		Sorting	Meetings (IOI18_meetings)	C++14	36 / 100	710 ms	196620 KiB

meetings

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

using namespace std;

const long long inf = 1e18;
const long long MAXN1 = 5007;
const long long MAXN = 75e4 + 7;

int n, q;
long long cost[MAXN1][MAXN1];

struct node{
	int m, l, r, cnt;

	node(){}
	node(int m, int l, int r){
		this->m = m;
		this->l = l;
		this->r = r;
		cnt = 1;
	}
};

node unite(node lvalue, node rvalue){
	node ret;

	ret.m = max(max(lvalue.m, rvalue.m), lvalue.r + rvalue.l);
	ret.l = (lvalue.l == lvalue.cnt) ? (lvalue.l + rvalue.l) : lvalue.l;
	ret.r = (rvalue.l == rvalue.cnt) ? (lvalue.r + rvalue.r) : rvalue.r;

	ret.m = max(ret.m, max(ret.l, ret.r));
	ret.cnt = lvalue.cnt + rvalue.cnt;

	return ret;
}

node st[4 * MAXN];
int a[MAXN];

void init(int idx, int l, int r){
	if(l == r){
		st[idx].m = st[idx].l = st[idx].r = (a[l] == 1);
		st[idx].cnt = 1;

		return;
	}

	int mid = (l + r) >> 1;

	init(2 * idx, l, mid);
	init(2 * idx + 1, mid + 1, r);

	st[idx] = unite(st[2 * idx], st[2 * idx + 1]);
}

node query(int idx, int l, int r, int sl, int sr){
	if(sl <= l && r <= sr){
		return st[idx];
	}
	if(l > sr || r < sl){
		return node(0, 0, 0);
	}

	int mid = (l + r) >> 1;

	node lvalue = query(2 * idx, l, mid, sl, sr);
	node rvalue = query(2 * idx + 1, mid + 1, r, sl, sr);

	return unite(lvalue, rvalue);
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	vector<long long> ret;

	n = (int)H.size();
	q = (int)L.size();

	if(n > 5000 || q > 5000){
		for(int i = 0; i < n; i++){
			a[i] = H[i];
		}

		init(1, 0, n - 1);

		for(int i = 0; i < q; i++){
			ret.push_back(2 * (R[i] - L[i] + 1) - query(1, 0, n - 1, L[i], R[i]).m);
		}

		return ret;
	}

	for(int i = 0; i < n; i++){
		long long mx = H[i];
		cost[i][i] = H[i];

		for(int j = i + 1; j < n; j++){
			mx = max(mx, (long long)H[j]);
			cost[i][j] = cost[i][j - 1] + mx; 
		}

		mx = H[i];
		for(int j = i - 1; j >= 0; j--){
			mx = max(mx, (long long)H[j]);
			cost[i][j] = cost[i][j + 1] + mx;
		}
	}

	for(int i = 0; i < q; i++){
		int l = L[i], r = R[i];
		long long ans = inf;

		for(int j = l; j <= r; j++){
			ans = min(ans, cost[j][l] + cost[j][r] - H[j]);
		}

		ret.push_back(ans);
	}

	return ret;
}

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