Submission #145669

#	Time	Username	Problem	Language	Result	Execution time	Memory
145669		Minnakhmetov	Meetings (IOI18_meetings)	C++14	19 / 100	775 ms	234760 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const ll INF = 1e18;
const int N1 = 5005, N2 = 1e5 + 5;
ll lp[N1][N1], rp[N1][N1];
int n, q;

vector<ll> slow(vector<int> a, vector<int> L, vector<int> R) {
	for (int i = 0; i < n; i++) {
  		ll cur = 0;
  		int mx = a[i];
  		for (int j = i - 1; j >= 0; j--) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			lp[j][i] = cur;
  		}

  		cur = 0;
  		mx = a[i];

  		for (int j = i + 1; j < n; j++) {
  			mx = max(mx, a[j]);
  			cur += mx;
  			rp[i][j] = cur;
  		}
  	}


  	vector<ll> ans(q);

  	for (int i = 0; i < q; i++) {
  		ll mn = INF;
  		for (int j = L[i]; j <= R[i]; j++) {
  			mn = min(mn, lp[L[i]][j] + rp[j][R[i]] + a[j]);
  		}
  		ans[i] = mn;
  	}
  	return ans;
}


int t[N2 * 4];

void build(int v, int L, int R, vector<pair<int, int>> &islands) {
	if (L == R) {
		t[v] = islands[L].second - islands[L].first + 1;
	}
	else {
		int m = (L + R) >> 1;
		build(v * 2, L, m, islands);
		build(v * 2 + 1, m + 1, R, islands);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
}

int que(int l, int r, int v, int L, int R) {
	if (l > r)
		return 0;
	if (l == L && r == R)
		return t[v];
	int m = (L + R) >> 1;
	return max(que(l, min(m, r), v * 2, L, m),
		que(max(m + 1, l), r, v * 2 + 1, m + 1, R));
}

vector<ll> binary(vector<int> a, vector<int> L, vector<int> R) {
	vector<pair<int, int>> islands;

	for (int i = 0, j = 0; i < n; i++) {
		if (a[i] == 1) {
			if (i == n - 1 || a[i + 1] != 1) {
				islands.push_back({ j, i });
			}
		}
		else {
			j = i + 1;
		}
	}

	build(1, 0, islands.size() - 1, islands);

	vector<ll> ans(q, 0);

	for (int i = 0; i < q; i++) {
		auto it = lower_bound(all(islands), make_pair(L[i] + 1, -1));
		int x, y, mx = 0;

		x = it - islands.begin();

		if (it != islands.begin()) {
			it--;
			if (it->second >= L[i]) {
				if (R[i] <= it->second) {
					ans[i] = R[i] - L[i] + 1;
					continue;
				}
				mx = max(mx, it->second - L[i] + 1);
			}
		}

		it = lower_bound(all(islands), make_pair(R[i] + 1, -1));

		if (it == islands.begin())
			continue;
		it--;
		y = int(it - islands.begin());

		if (it->second >= R[i]) {
			mx = max(mx, R[i] - it->first + 1);
			y--;
		}

		mx = max(mx, que(x, y, 1, 0, islands.size() - 1));

		ans[i] = (R[i] - L[i] + 1) * 2 - mx;
	}

	return ans;
}

std::vector<long long> minimum_costs(std::vector<int> a, std::vector<int> L,
                                     std::vector<int> R) {
	n = a.size(), q = L.size();

  	if (n < N1 && q < N1) {
  		return slow(a, L, R); 
  	}

  	return binary(a, L, R);
}

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