제출 #1069128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069128		Joshua_Andersson	모임들 (IOI18_meetings)	C++14	17 / 100	82 ms	18780 KiB

meetings

#include "meetings.h"

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

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

typedef vector<ll> vll;

struct info
{
	ll l=0, r=0, m=0, w=1;
};

info merge(info a, info b)
{
	info ret;
	ret.l = a.l;
	if (a.l == a.w) ret.l += b.l;
	ret.r = b.r;
	if (b.r == b.w) ret.r += a.r;

	ret.m = max(a.m, b.m);
	ret.m = max(ret.m, a.r + b.l);
	ret.m = max(ret.m, ret.l);
	ret.m = max(ret.m, ret.r);


	ret.w = a.w + b.w;

	return ret;
}

struct Tree
{
	vector<info> tree;
	Tree(vll nums) : tree(sz(nums) * 4)
	{
		build(1, 0, sz(nums) - 1, nums);
	}
	
	void build(int x, int l, int r, vll& nums)
	{
		if (l==r)
		{
			tree[x] = info();
			if (nums[l] == 1) tree[x].l = tree[x].r = tree[x].m = 1;
		}
		else
		{
			int mid = (l + r) / 2;
			build(x * 2, l, mid, nums);
			build(x * 2 + 1, mid + 1, r, nums);
			tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
		}
	}

	info query(int x, int l, int r, int ql, int qr)
	{
		if (l > qr || r < ql) return info();
		if (l >= ql && r <= qr) return tree[x];
		int mid = (l + r) / 2;
		return merge(query(x * 2, l, mid, ql, qr), query(x * 2 + 1, mid + 1, r, ql, qr));
	}
};

vll minimum_costs(vi H, std::vector<int> L, std::vector<int> R)
{
	vll h(H.begin(), H.end());
	Tree tree(h);
	int n = sz(h);
	int q = sz(L);
	vll ret(q);
	rep(qu, q)
	{
		int l = L[qu];
		int r = R[qu];
		ret[qu] = 2*(r-l+1)-tree.query(1,0,n-1,l,r).m;
	}
	return ret;
}

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