Submission #96707

#	Time	Username	Problem	Language	Result	Execution time	Memory
96707		diamond_duke	Meetings (IOI18_meetings)	C++11	100 / 100	3896 ms	539136 KiB

meetings

#include "meetings.h"
#include <functional>
using ll = long long;
struct segT
{
	struct data
	{
		int st, en;
		ll val_l, val_r, k, b;
		bool cov;
		data(ll _k = 0, ll _b = 0, bool flg = false) : k(_k), b(_b), cov(flg) {}
		inline void paint(data x)
		{
			if (x.cov)
			{
				val_l = val_r = k = b = 0;
				cov = true;
			}
			k += x.k;
			b += x.b;
			val_l += x.k * st + x.b;
			val_r += x.k * en + x.b;
		}
	} seg[3000005];
	int n;
	inline void push_down(int u)
	{
		if (seg[u].cov || seg[u].k || seg[u].b)
		{
			seg[u << 1].paint(seg[u]);
			seg[u << 1 | 1].paint(seg[u]);
			seg[u].k = seg[u].b = 0;
			seg[u].cov = false;
		}
	}
	inline void push_up(int u)
	{
		seg[u].val_l = seg[u << 1].val_l;
		seg[u].val_r = seg[u << 1 | 1].val_r;
	}
	void build(int u, int l, int r)
	{
		seg[u].st = l;
		seg[u].en = r;
		if (l == r)
			return;
		int m = l + r >> 1;
		build(u << 1, l, m);
		build(u << 1 | 1, m + 1, r);
	}
	void modify(int u, int l, int r, int L, int R, ll x)
	{
		if (L <= l && r <= R)
		{
			seg[u].paint({0, x});
			return;
		}
		push_down(u);
		int m = l + r >> 1;
		if (L <= m)
			modify(u << 1, l, m, L, R, x);
		if (m < R)
			modify(u << 1 | 1, m + 1, r, L, R, x);
		push_up(u);
	}
	void add_line(int u, int l, int r, int L, int R, ll k, ll b)
	{
		if (L <= l && r <= R)
		{
			ll new_l = k * l + b, new_r = k * r + b;
			if (new_l >= seg[u].val_l && new_r >= seg[u].val_r)
				return;
			if (new_l <= seg[u].val_l && new_r <= seg[u].val_r)
			{
				seg[u].paint({k, b, true});
				return;
			}
		}
		push_down(u);
		int m = l + r >> 1;
		if (L <= m)
			add_line(u << 1, l, m, L, R, k, b);
		if (m < R)
			add_line(u << 1 | 1, m + 1, r, L, R, k, b);
		push_up(u);
	}
	ll query(int u, int l, int r, int pos)
	{
		if (l == r)
			return seg[u].val_l;
		push_down(u);
		int m = l + r >> 1;
		if (pos <= m)
			return query(u << 1, l, m, pos);
		return query(u << 1 | 1, m + 1, r, pos);
	}
	inline void init(int _n)
	{
		n = _n;
		build(1, 0, n - 1);
	}
	inline void modify(int L, int R, ll x) { modify(1, 0, n - 1, L, R, x); }
	inline void add_line(int L, int R, ll k, ll b) { add_line(1, 0, n - 1, L, R, k, b); }
	inline ll query(int pos) { return query(1, 0, n - 1, pos); }
} pre, suf;
std::vector<ll> minimum_costs(std::vector<int> arr, std::vector<int> ql, std::vector<int> qr)
{
	int n = arr.size(), q = ql.size();
	std::vector<int> lg(n + 1);
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i >> 1] + 1;
	std::vector<std::vector<int> > mx(lg[n] + 1, std::vector<int>(n));
	for (int i = 0; i < n; i++)
		mx[0][i] = i;
	auto larger = [&] (int x, int y) { return arr[x] > arr[y] ? x : y; };
	for (int i = 1; i <= lg[n]; i++)
	{
		for (int j = 0; j + (1 << i) <= n; j++)
			mx[i][j] = larger(mx[i - 1][j], mx[i - 1][j + (1 << i - 1)]);
	}
	auto query = [&] (int l, int r)
	{
		int len = lg[r - l + 1];
		return larger(mx[len][l], mx[len][r - (1 << len) + 1]);
	};
	std::vector<ll> ans(q);
	std::vector<std::vector<int> > qry(n);
	for (int i = 0; i < q; i++)
		qry[query(ql[i], qr[i])].push_back(i);
	pre.init(n);
	suf.init(n);
	std::function<void (int, int)> solve = [&] (int l, int r)
	{
		if (l > r)
			return;
		int m = query(l, r);
		solve(l, m - 1);
		solve(m + 1, r);
		for (auto i : qry[m])
		{
			ans[i] = (ll)arr[m] * (qr[i] - ql[i] + 1);
			if (ql[i] < m)
				ans[i] = std::min(suf.query(ql[i]) + (ll)arr[m] * (qr[i] - m + 1), ans[i]);
			if (m < qr[i])
				ans[i] = std::min(pre.query(qr[i]) + (ll)arr[m] * (m - ql[i] + 1), ans[i]);
		}
		ll val_pre = arr[m] + (l < m ? pre.query(m - 1) : 0),
		   val_suf = arr[m] + (m < r ? suf.query(m + 1) : 0);
		pre.modify(m, m, val_pre);
		suf.modify(m, m, val_suf);
		if (l < m)
		{
			suf.modify(l, m - 1, (ll)arr[m] * (r - m + 1));
			suf.add_line(l, m - 1, -arr[m], val_suf + (ll)arr[m] * m);
		}
		if (m < r)
		{
			pre.modify(m + 1, r, (ll)arr[m] * (m - l + 1));
			pre.add_line(m + 1, r, arr[m], val_pre - (ll)arr[m] * m);
		}
	};
	solve(0, n - 1);
	return ans;
}

Compilation message (stderr)

meetings.cpp: In member function 'void segT::build(int, int, int)':
meetings.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
meetings.cpp: In member function 'void segT::modify(int, int, int, int, int, ll)':
meetings.cpp:59:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
meetings.cpp: In member function 'void segT::add_line(int, int, int, int, int, ll, ll)':
meetings.cpp:80:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
meetings.cpp: In member function 'll segT::query(int, int, int, int)':
meetings.cpp:92:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:119:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    mx[i][j] = larger(mx[i - 1][j], mx[i - 1][j + (1 << i - 1)]);
                                                        ~~^~~

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