Submission #581906

#	Time	Username	Problem	Language	Result	Execution time	Memory
581906		8e7	Meetings (IOI18_meetings)	C++17	19 / 100	883 ms	4000 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 100005
#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<<60;
int h[maxn], lef[maxn], rig[maxn];
ll ls[maxn], rs[maxn];
struct segtree{
	ll seg[maxn], tag[maxn];
	bool tagged[maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		seg[cur] = tag[cur] = 0;
		tagged[cur] = 0;
		if (r - l == 1) {
			seg[cur] = ls[l] + rs[l] - h[l];
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
		seg[cur] = min(seg[cur*2], seg[cur*2+1]);
	}
	void modify(int cur, int l, int r, int ql, int qr, ll v) {
		if (r <= l || ql >= r || qr <= l) return;
		tagged[cur] = 1;
		if (ql <= l && qr >= r) {
			tag[cur] += v;
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, v);
		modify(cur*2+1, m, r, ql, qr, v);
		seg[cur] = min(seg[cur*2] + tag[cur*2], seg[cur*2+1] + tag[cur*2+1]);
	}
	void undo(int cur, int l, int r) {
		tagged[cur] = 0;
		tag[cur] = 0;
		if (r - l > 1) {
			int m = (l + r) / 2;
			if (tagged[cur*2]) undo(cur*2, l, m);
			if (tagged[cur*2+1]) undo(cur*2+1, m, r);
			seg[cur] = min(seg[cur*2], seg[cur*2+1]);
		}
	}
	ll query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return inf;
		if (ql <= l && qr >= r) return seg[cur] + tag[cur];
		int m = (l + r) / 2;
		return min(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr)) + tag[cur];
	}
} tr;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
		std::vector<int> R) {

	int n = H.size(), q = L.size();
	for (int i = 0;i < n;i++) h[i+1] = H[i];
	for (int i = 0;i < q;i++) {
		L[i]++, R[i]++; //[L, R]
	}
	h[0] = h[n+1] = 1<<30;
	stack<int> stk;	
	stk.push(0);
	for (int i = 1;i <= n+1;i++) {
		while (stk.size() && h[i] >= h[stk.top()]) stk.pop();	
		if (stk.size()) lef[i] = stk.top();
		ls[i] = (ll)h[i] * (i - lef[i]) + ls[lef[i]];
		stk.push(i);
	}
	while (stk.size()) stk.pop();
	stk.push(n+1);
	for (int i = n;i >= 0;i--) {
		while (stk.size() && h[i] >= h[stk.top()]) stk.pop();	
		if (stk.size()) rig[i] = stk.top();
		rs[i] = (ll)h[i] * (rig[i] - i) + rs[rig[i]];
		stk.push(i);
	}
	/*
	pary(lef + 1, lef + n + 1);
	pary(rig + 1, rig + n + 1);
	pary(ls + 1, ls + n + 1);
	pary(rs + 1, rs + n + 1);
	*/
	tr.init(1, 1, n+1);
	vector<ll> ret(q);
	vector<int> rm(n);
	for (int i = 0;i < q;i++) {
		ll ans = inf;
			
		for (int j = R[i];j >= L[i];j--) {
			rm[j] = j;
			if (j < R[i] && h[rm[j+1]] > h[rm[j]]) rm[j] = rm[j+1]; 
		}
		int lm = L[i];
		debug(i);
		for (int j = L[i];j <= R[i];j++) {
			ll cur = ls[j] + rs[j] - h[j];
			if (h[j] > h[lm]) lm = j;
			cur -= ls[lm] - (ll)h[lm] * (lm - L[i] + 1);
			cur -= rs[rm[j]] - (ll)h[rm[j]] * (R[i] - rm[j] + 1);
			//debug(j, lm, rm[j], cur);
			ans = min(ans, cur);
		}
		ret[i] = ans;
		/*
		int cur = L[i];
		//debug(i);
		while (cur <= R[i]) {
			//debug(cur, min(R[i]+1, rig[cur]), -ls[cur] + (ll)h[cur] * (cur - L[i]+1));
			tr.modify(1, 1, n+1, cur, min(R[i]+1, rig[cur]), -ls[cur] + (ll)h[cur] * (cur - L[i]+1));
			cur = rig[cur];
		}
		cur = R[i];	
		while (cur >= L[i]) {
			//debug(max(L[i], lef[cur]+1), cur+1, -rs[cur] + (ll)h[cur] * (R[i] - cur+1));
			tr.modify(1, 1, n+1, max(L[i], lef[cur]+1), cur+1, -rs[cur] + (ll)h[cur] * (R[i] - cur+1));
			cur = lef[cur];
		}
		ret[i] = tr.query(1, 1, n+1, L[i], R[i]+1);
		tr.undo(1, 1, n+1);
		*/
	}

	return ret;
}
/*

4 2
2 4 3 5
0 2
1 3
*/

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
meetings.cpp:111:3: note: in expansion of macro 'debug'
  111 |   debug(i);
      |   ^~~~~

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