Submission #581907

#	Time	Username	Problem	Language	Result	Execution time	Memory
581907		8e7	Meetings (IOI18_meetings)	C++17	19 / 100	5539 ms	6956 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 lef[maxn], rig[maxn];
ll ls[maxn], rs[maxn];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
		std::vector<int> R) {

	int q = L.size();
	vector<ll> ret(q, 0);
	for (int id = 0;id < q;id++) {
		vector<int> h;
		h.push_back(1<<30);
		for (int i = L[id];i <= R[id];i++) h.push_back(H[i]);
		h.push_back(1<<30);
		int n = h.size() - 2;
		for (int i = 0;i <= n+1;i++) {
			ls[i] = rs[i] = 0;
		}
		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);
		}
		ll ans = inf;
		for (int i = 1;i <=n;i++) {
			debug(ls[i], rs[i], h[i]);
			ans = min(ans, ls[i] + rs[i] - h[i]); 
		}
		debug();
		ret[id] = ans;
	}
	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:58:4: note: in expansion of macro 'debug'
   58 |    debug(ls[i], rs[i], h[i]);
      |    ^~~~~
meetings.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
meetings.cpp:61:3: note: in expansion of macro 'debug'
   61 |   debug();
      |   ^~~~~

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