Submission #585709

#	Time	Username	Problem	Language	Result	Execution time	Memory
585709		8e7	Meetings (IOI18_meetings)	C++17	100 / 100	3103 ms	227476 KiB

meetings

#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 (stderr)

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40