oj.uz

답안 #585709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585709 2022-06-29T08:55:36 Z 8e7 모임들 (IOI18_meetings) C++17
100 / 100
 3103 ms 227476 KB 
#include "meetings.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 750005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<62;

struct query{
	int l, r, id;
	query(){l = r = id = 0;}
	query(int a, int b, int c){l = a, r = b, id = c;}	
};

bool TYPE = 0;
struct segtree{
	pii seg[4*maxn];
	void init(int cur, int l, int r, vector<int> &h) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = {h[l], TYPE ? -l : l};
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m, h), init(cur*2+1, m, r, h);
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return {-1, 0};
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		return max(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
} tr;
struct LINE{
	ll m, k;
	LINE() {m = 0, k = 0;}
	LINE(ll x, ll y){m = x, k = y;}
	ll val(ll x){return m*x + k;}
} line[maxn];

int lc[maxn], rc[maxn], lef[maxn], rig[maxn];
vector<int> ord;
vector<query> qs[maxn];

void dfs(int n) {
	if (lc[n] != -1) dfs(lc[n]);
	if (rc[n] != -1) dfs(rc[n]);
	ord.push_back(n);
}

set<int> se;
ll tag[maxn];
vector<ll> solve(vector<int> h, vector<query> que) {
	int n = h.size(), q = que.size();
	
	tr.init(1, 0, n, h);
	se.clear();
	for (int i = 0;i < n;i++) {
		se.insert(i);
		lc[i] = rc[i] = -1;
		lef[i] = 0, rig[i] = n - 1;
		tag[i] = 0;
		line[i] = LINE();
		qs[i].clear();
	}
	se.insert(n);
	for (auto x:que) {
		int ind = tr.query(1, 0, n, x.l, x.r+1).ss;
		if (TYPE) ind = -ind;
		qs[ind].push_back(x);	
	}

	stack<int> stk;	
	for (int i = 0;i < n;i++) {
		while (stk.size() && (TYPE ? h[i] > h[stk.top()] : h[i] >= h[stk.top()])) {
			lc[i] = stk.top();
			rig[stk.top()] = i-1;
			stk.pop();
		}
		if (stk.size()) {
			rc[stk.top()] = i;
			lef[i] = stk.top()+1;
		}
		stk.push(i);
	}
	
	int root = 0;		
	while (stk.size() > 1) stk.pop();
	root = stk.top();

	ord.clear();
	dfs(root);
	
	vector<ll> ret(q, inf);
	
	debug();
	pary(h.begin(), h.end());
	for (int i:ord) {

		for (auto [l, r, id]:qs[i]) {
			ret[id] = (ll)(h[i]) * (r - l + 1);
			if (rc[i] != -1) {
				int ind = *prev(se.upper_bound(r));
				debug(l, r, rc[i], ind, line[ind].m, line[ind].k, tag[rc[i]], (ll)h[i] * (i - l + 1) + line[ind].val(r) + tag[rc[i]]);
				ret[id] = min(ret[id], (ll)h[i] * (i - l + 1) + line[ind].val(r) + tag[rc[i]]);
			}
		}

		ll delta = (ll)(i - lef[i] + 1) * h[i];

		bool hasl = lc[i] != -1, hasr = rc[i] != -1;
		if (hasl) {
			int ind = *prev(se.lower_bound(i));
			line[i].k = h[i] + line[ind].val(i-1) + tag[lc[i]];
		} else {
			line[i].k = h[i];
		}
		//debug("line", lef[i], i, line[i].k);
		if (hasl || hasr) {
			if (rc[i] != -1) tag[rc[i]] += delta;
			if (i - lef[i] < rig[i] - i) {
				for (int j = lef[i];j < i;j++) {
					line[j].k += tag[lc[i]] - tag[rc[i]];
				}
				line[i].k += tag[i] - tag[rc[i]];

				tag[i] = tag[rc[i]];
			} else {
				for (int j = i+1;j <= rig[i];j++) {
					line[j].k += tag[rc[i]] - tag[lc[i]];
				}
				line[i].k += tag[i] - tag[lc[i]];
				tag[i] = tag[lc[i]];
			}
		}
		if (hasr) {
			LINE mi = LINE(h[i], line[i].val(i) - (ll)i * h[i]);
			auto it = next(se.lower_bound(i));	
			
			auto div = [&] (ll a, ll b){
				assert(b != 0);
				if (b < 0) a = -a, b = -b;
				return a / b + 1;
			};
			vector<int> rem;
			while (*it < rig[i]+1) {
				int r = (*next(it)) - 1, l = *it;
				if (mi.val(r) <= line[*it].val(r)) {
					rem.push_back(l);
				} else if (mi.val(l) > line[l].val(l)) {
					break;
				} else {
					rem.push_back(l);
					int pnt = div(line[l].k - mi.k, mi.m - line[l].m);
					se.insert(pnt);
					line[pnt] = line[l];
					break;
				}
				it = next(it);
			}
			for (auto j:rem) se.erase(j);
			line[i] = mi;
		}
		debug(i, line[i].m, line[i].k, tag[i]);
	}
	return ret;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
		std::vector<int> R) {

	vector<query> que;
	int n = H.size(), q = L.size();
	for (int i = 0;i < q;i++) {
		que.push_back(query(L[i], R[i], i));
	}

	TYPE = 0;
	vector<ll> ret(q, inf);
	vector<ll> tmp = solve(H, que);
	ret = tmp;

	reverse(H.begin(), H.end());
	for (int i = 0;i < q;i++) {
		que[i].l = n - 1 - que[i].l, que[i].r = n - 1 - que[i].r;
		swap(que[i].l, que[i].r);
	}
	TYPE = 1;
	tmp = solve(H, que);
	for (int i = 0;i < q;i++) ret[i] = min(ret[i], tmp[i]);

	return ret;
}
/*


6 3
2 4 3 5 3 1
0 5
1 3
2 5

(24, 12, 14)

10 4
1 2 1 2 1 1 1 2 1 1
0 9
0 5
1 8
2 6

(17, 10, 13, 7)

10 1
9 1 7 8 2 8 2 3 1 10 
0 9
*/

Compilation message

meetings.cpp: In function 'std::vector<long long int> solve(std::vector<int>, std::vector<query>)':
meetings.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
meetings.cpp:112:2: note: in expansion of macro 'debug'
  112 |  debug();
      |  ^~~~~
meetings.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
meetings.cpp:113:2: note: in expansion of macro 'pary'
  113 |  pary(h.begin(), h.end());
      |  ^~~~
meetings.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
meetings.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(l, r, rc[i], ind, line[ind].m, line[ind].k, tag[rc[i]], (ll)h[i] * (i - l + 1) + line[ind].val(r) + tag[rc[i]]);
      |     ^~~~~
meetings.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
meetings.cpp:180:3: note: in expansion of macro 'debug'
  180 |   debug(i, line[i].m, line[i].k, tag[i]);
      |   ^~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 29652 KB Output is correct
2 Correct 18 ms 30028 KB Output is correct
3 Correct 16 ms 30036 KB Output is correct
4 Correct 18 ms 30060 KB Output is correct
5 Correct 20 ms 29960 KB Output is correct
6 Correct 16 ms 30036 KB Output is correct
7 Correct 20 ms 30156 KB Output is correct
8 Correct 15 ms 30036 KB Output is correct
9 Correct 16 ms 30076 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 29652 KB Output is correct
2 Correct 18 ms 30028 KB Output is correct
3 Correct 16 ms 30036 KB Output is correct
4 Correct 18 ms 30060 KB Output is correct
5 Correct 20 ms 29960 KB Output is correct
6 Correct 16 ms 30036 KB Output is correct
7 Correct 20 ms 30156 KB Output is correct
8 Correct 15 ms 30036 KB Output is correct
9 Correct 16 ms 30076 KB Output is correct
10 Correct 23 ms 30868 KB Output is correct
11 Correct 22 ms 30836 KB Output is correct
12 Correct 23 ms 30856 KB Output is correct
13 Correct 22 ms 30932 KB Output is correct
14 Correct 29 ms 30984 KB Output is correct
15 Correct 28 ms 30868 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 29708 KB Output is correct
2 Correct 76 ms 35588 KB Output is correct
3 Correct 250 ms 52080 KB Output is correct
4 Correct 236 ms 49964 KB Output is correct
5 Correct 220 ms 51968 KB Output is correct
6 Correct 211 ms 52328 KB Output is correct
7 Correct 285 ms 52900 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 29708 KB Output is correct
2 Correct 76 ms 35588 KB Output is correct
3 Correct 250 ms 52080 KB Output is correct
4 Correct 236 ms 49964 KB Output is correct
5 Correct 220 ms 51968 KB Output is correct
6 Correct 211 ms 52328 KB Output is correct
7 Correct 285 ms 52900 KB Output is correct
8 Correct 251 ms 50400 KB Output is correct
9 Correct 205 ms 52020 KB Output is correct
10 Correct 238 ms 52264 KB Output is correct
11 Correct 235 ms 51896 KB Output is correct
12 Correct 222 ms 51836 KB Output is correct
13 Correct 235 ms 52324 KB Output is correct
14 Correct 305 ms 54292 KB Output is correct
15 Correct 215 ms 51832 KB Output is correct
16 Correct 236 ms 53836 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 29652 KB Output is correct
2 Correct 18 ms 30028 KB Output is correct
3 Correct 16 ms 30036 KB Output is correct
4 Correct 18 ms 30060 KB Output is correct
5 Correct 20 ms 29960 KB Output is correct
6 Correct 16 ms 30036 KB Output is correct
7 Correct 20 ms 30156 KB Output is correct
8 Correct 15 ms 30036 KB Output is correct
9 Correct 16 ms 30076 KB Output is correct
10 Correct 23 ms 30868 KB Output is correct
11 Correct 22 ms 30836 KB Output is correct
12 Correct 23 ms 30856 KB Output is correct
13 Correct 22 ms 30932 KB Output is correct
14 Correct 29 ms 30984 KB Output is correct
15 Correct 28 ms 30868 KB Output is correct
16 Correct 17 ms 29708 KB Output is correct
17 Correct 76 ms 35588 KB Output is correct
18 Correct 250 ms 52080 KB Output is correct
19 Correct 236 ms 49964 KB Output is correct
20 Correct 220 ms 51968 KB Output is correct
21 Correct 211 ms 52328 KB Output is correct
22 Correct 285 ms 52900 KB Output is correct
23 Correct 251 ms 50400 KB Output is correct
24 Correct 205 ms 52020 KB Output is correct
25 Correct 238 ms 52264 KB Output is correct
26 Correct 235 ms 51896 KB Output is correct
27 Correct 222 ms 51836 KB Output is correct
28 Correct 235 ms 52324 KB Output is correct
29 Correct 305 ms 54292 KB Output is correct
30 Correct 215 ms 51832 KB Output is correct
31 Correct 236 ms 53836 KB Output is correct
32 Correct 2161 ms 199392 KB Output is correct
33 Correct 1783 ms 200348 KB Output is correct
34 Correct 2150 ms 205080 KB Output is correct
35 Correct 2436 ms 200928 KB Output is correct
36 Correct 1777 ms 203312 KB Output is correct
37 Correct 2303 ms 205288 KB Output is correct
38 Correct 2657 ms 219640 KB Output is correct
39 Correct 2615 ms 219684 KB Output is correct
40 Correct 2345 ms 206240 KB Output is correct
41 Correct 2572 ms 227476 KB Output is correct
42 Correct 3103 ms 224380 KB Output is correct
43 Correct 3052 ms 224164 KB Output is correct
44 Correct 3015 ms 218292 KB Output is correct