Submission #145688

#	Time	Username	Problem	Language	Result	Execution time	Memory
145688		Minnakhmetov	Meetings (IOI18_meetings)	C++14	19 / 100	798 ms	263064 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, K = 2;
ll lp[N1][N1], rp[N1][N1];
int n, q;
vector<int> a;

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;
}


struct Node {
	int mx;
	ll lp[K], rp[K], val[K][K];

	Node() {
		for (int i = 0; i < K; i++) {
			for (int j = 0; j < K; j++) {
				val[i][j] = INF;
			}
		}
		fill(lp, lp + K, 0);
		fill(rp, rp + K, 0);
		mx = 0;
	}
} t[N2 * 4];

Node operator + (Node a, Node b) {
	Node c;
	c.mx = max(a.mx, b.mx);

	for (int i = 0; i < K; i++) {
		c.rp[i] = b.rp[i] + a.rp[b.mx];
		c.lp[i] = a.lp[i] + b.lp[a.mx];
	}

	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			c.val[i][b.mx] = min(c.val[i][b.mx], a.val[i][j] + b.lp[j]);
			c.val[a.mx][j] = min(c.val[a.mx][j], b.val[i][j] + a.rp[i]);
		}
	}

	return c;
}


void build(int v, int L, int R) {
	if (L == R) {
		t[v].val[a[L]][a[L]] = a[L];
		for (int i = 0; i <= a[L]; i++)
			t[v].lp[i] = t[v].rp[i] = a[L];
		for (int i = a[L] + 1; i < K; i++) {
			t[v].lp[i] = t[v].rp[i] = i;
		}
		t[v].mx = a[L];
	}
	else {
		int m = (L + R) >> 1;
		build(v * 2, L, m);
		build(v * 2 + 1, m + 1, R);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
	// cout << L << " " << R << " : ";
	// for (int i = 0; i < 2; i++) {
	// 	for (int j = 0; j < 2; j++) {
	// 		cout << i << " " << j << " = " << t[v].val[i][j] << "\n";
	// 	}
	// }
	// cout << "\n\n";
	// for (int i = 0; i < 2; i++)
	// 	cout << t[v].lp[i] << " ";
	// cout << "\n";
	// for (int i = 0; i < 2; i++)
	// 	cout << t[v].rp[i] << " ";
	// cout << "\n";
	// cout << "\n";
}

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

vector<ll> solveWhenLessThan20(vector<int> L, vector<int> R) {
	for (int &x : a)
		x--;
	build(1, 0, n - 1);

	vector<ll> ans(q, 0);

	for (int i = 0; i < q; i++) {
		auto res = que(L[i], R[i], 1, 0, n - 1);
		ll mn = INF;
		for (int x = 0; x < K; x++) {
			for (int y = 0; y < K; y++) {
				mn = min(mn, res.val[x][y]);
			}
		}
		ans[i] = mn + R[i] - L[i] + 1;
	}
	return ans;
}

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

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

  	return solveWhenLessThan20(L, R);
}

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