oj.uz

답안 #96707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96707 2019-02-11T07:34:04 Z diamond_duke 모임들 (IOI18_meetings) C++11
100 / 100
 3896 ms 539136 KB 
#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

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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 282100 KB Output is correct
2 Correct 221 ms 282380 KB Output is correct
3 Correct 226 ms 282400 KB Output is correct
4 Correct 227 ms 282388 KB Output is correct
5 Correct 226 ms 282340 KB Output is correct
6 Correct 226 ms 282676 KB Output is correct
7 Correct 219 ms 282304 KB Output is correct
8 Correct 219 ms 282708 KB Output is correct
9 Correct 221 ms 282512 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 282100 KB Output is correct
2 Correct 221 ms 282380 KB Output is correct
3 Correct 226 ms 282400 KB Output is correct
4 Correct 227 ms 282388 KB Output is correct
5 Correct 226 ms 282340 KB Output is correct
6 Correct 226 ms 282676 KB Output is correct
7 Correct 219 ms 282304 KB Output is correct
8 Correct 219 ms 282708 KB Output is correct
9 Correct 221 ms 282512 KB Output is correct
10 Correct 228 ms 282728 KB Output is correct
11 Correct 226 ms 282764 KB Output is correct
12 Correct 226 ms 282732 KB Output is correct
13 Correct 225 ms 282756 KB Output is correct
14 Correct 229 ms 283200 KB Output is correct
15 Correct 226 ms 282748 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 282108 KB Output is correct
2 Correct 268 ms 285104 KB Output is correct
3 Correct 507 ms 305220 KB Output is correct
4 Correct 478 ms 295420 KB Output is correct
5 Correct 459 ms 307164 KB Output is correct
6 Correct 478 ms 307944 KB Output is correct
7 Correct 513 ms 310332 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 282108 KB Output is correct
2 Correct 268 ms 285104 KB Output is correct
3 Correct 507 ms 305220 KB Output is correct
4 Correct 478 ms 295420 KB Output is correct
5 Correct 459 ms 307164 KB Output is correct
6 Correct 478 ms 307944 KB Output is correct
7 Correct 513 ms 310332 KB Output is correct
8 Correct 502 ms 296240 KB Output is correct
9 Correct 415 ms 296244 KB Output is correct
10 Correct 452 ms 296348 KB Output is correct
11 Correct 480 ms 295380 KB Output is correct
12 Correct 416 ms 295388 KB Output is correct
13 Correct 444 ms 295424 KB Output is correct
14 Correct 512 ms 305380 KB Output is correct
15 Correct 456 ms 295232 KB Output is correct
16 Correct 519 ms 305748 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 282100 KB Output is correct
2 Correct 221 ms 282380 KB Output is correct
3 Correct 226 ms 282400 KB Output is correct
4 Correct 227 ms 282388 KB Output is correct
5 Correct 226 ms 282340 KB Output is correct
6 Correct 226 ms 282676 KB Output is correct
7 Correct 219 ms 282304 KB Output is correct
8 Correct 219 ms 282708 KB Output is correct
9 Correct 221 ms 282512 KB Output is correct
10 Correct 228 ms 282728 KB Output is correct
11 Correct 226 ms 282764 KB Output is correct
12 Correct 226 ms 282732 KB Output is correct
13 Correct 225 ms 282756 KB Output is correct
14 Correct 229 ms 283200 KB Output is correct
15 Correct 226 ms 282748 KB Output is correct
16 Correct 219 ms 282108 KB Output is correct
17 Correct 268 ms 285104 KB Output is correct
18 Correct 507 ms 305220 KB Output is correct
19 Correct 478 ms 295420 KB Output is correct
20 Correct 459 ms 307164 KB Output is correct
21 Correct 478 ms 307944 KB Output is correct
22 Correct 513 ms 310332 KB Output is correct
23 Correct 502 ms 296240 KB Output is correct
24 Correct 415 ms 296244 KB Output is correct
25 Correct 452 ms 296348 KB Output is correct
26 Correct 480 ms 295380 KB Output is correct
27 Correct 416 ms 295388 KB Output is correct
28 Correct 444 ms 295424 KB Output is correct
29 Correct 512 ms 305380 KB Output is correct
30 Correct 456 ms 295232 KB Output is correct
31 Correct 519 ms 305748 KB Output is correct
32 Correct 2622 ms 389260 KB Output is correct
33 Correct 2043 ms 392016 KB Output is correct
34 Correct 2262 ms 390204 KB Output is correct
35 Correct 2846 ms 389696 KB Output is correct
36 Correct 2015 ms 390504 KB Output is correct
37 Correct 2269 ms 390544 KB Output is correct
38 Correct 3259 ms 464848 KB Output is correct
39 Correct 3542 ms 464808 KB Output is correct
40 Correct 3031 ms 397616 KB Output is correct
41 Correct 3440 ms 538076 KB Output is correct
42 Correct 3802 ms 539124 KB Output is correct
43 Correct 3896 ms 539136 KB Output is correct
44 Correct 3662 ms 464928 KB Output is correct