Submission #1024986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024986		fv3	Meetings (IOI18_meetings)	C++14	17 / 100	376 ms	20684 KiB

meetings

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

using namespace std;
typedef long long ll;


struct range
{
	int l, r = -1;
	bool operator<(const range other) const
	{
		if (r - l > other.r - other.l)
			return true;
		return r - l == other.r - other.l && l < other.l;
	}
	bool operator==(const range other) const
	{
		return l == other.l && r == other.r;
	}
};
struct node
{
	vector<range> v;
};
node merge(node a, node b)
{
	a.v.insert(a.v.end(), b.v.begin(), b.v.end());
	sort(a.v.begin(), a.v.end());
	for (int i = a.v.size() - 2; i >= 0; i--)
	{
		if (a.v[i] == a.v[i+1])
		{
			a.v.erase(a.v.begin() + i + 1);
		}
	}

	a.v.resize(3);
	return {a.v};
}
node emptyNode = {{{0, -1}, {0, -1}, {0, -1}}};

int N, nt = 1;
vector<node> st;

node getRange(int l, int r, int k, int x, int y)
{
	if (r < x || l > y) return emptyNode;
	if (x >= l && y <= r) return st[k];
	int c = (x + y) / 2;
	return merge(getRange(l, r, k*2, x, c), getRange(l, r, k*2|1, c+1, y));
}

ll valueOf(range n, int l, int r)
{
	if (n.r == -1) return -1;
	return min(n.r, r) - max(n.l, l);
}

ll solve(int l, int r)
{
	node best = getRange(l, r, 1, 0, nt - 1); 
	return max({valueOf(best.v[0], l, r), valueOf(best.v[1], l, r), valueOf(best.v[2], l, r)});
}

void makeST(vector<int>&H)
{
	vector<range> v;
	int last = N;
	for (int i = 0; i < N; i++)
	{
		if (H[i] == 2) continue;

		if (last == N)
			last = i;
		if (H[i+1] == 2)
		{
			v.push_back({last, i});
			last = N;
		}
	}

	while (nt < N)
		nt <<= 1;
	st = vector<node>(2 * nt, {vector<range>(3)});

	for (auto r : v)
	{
		for (int i = r.l; i <= r.r; i++)
			st[nt+i].v[0] = r;
	}

	for (int i = nt - 1; i >= 1; i--)
		st[i] = merge(st[i*2], st[i*2|1]);

	/*for (int i = 1; i < 2 * nt; i++)
	{
		cerr << i << " {("<< st[i].v[0].l << ", " << st[i].v[0].r << "), (" 
					<< st[i].v[1].l << ", " << st[i].v[1].r << "), (" 
					<< st[i].v[2].l << ", " << st[i].v[2].r << ")}\n"; 
	}*/
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	const int Q = L.size();
	N = H.size();
	H.push_back(2);

	makeST(H);

	vector<ll> C;
	for (int q = 0; q < Q; q++)
	{
		C.push_back(2ll * (R[q] - L[q] + 1) - solve(L[q], R[q]) - 1ll);
	}
	return C;
}

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