Submission #830842

#	Time	Username	Problem	Language	Result	Execution time	Memory
830842		tranxuanbach	Meetings (IOI18_meetings)	C++17	19 / 100	5581 ms	6716 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())

using ll = long long;

struct query{
	int l, r;
};

struct monotonic_stack{
	vector <pair <int, int>> st;
	ll sum;

	monotonic_stack(){
		st.clear();
		sum = 0;
	}

	void insert(int x){
		int len = 1;
		while (not st.empty() and st.back().first <= x){
			len += st.back().second;
			sum -= (ll)st.back().first * st.back().second;
			st.pop_back();
		}
		st.emplace_back(x, len);
		sum += (ll)x * len;
	}
};

const int N = 750'000 + 5;

int n, q;
int a[N];
query b[N];

ll ans[N];

ll tans[N];

vector <ll> minimum_costs(vector <int> _a, vector <int> _l, vector <int> _r){
	n = isz(_a);
	q = isz(_l);
	For(i, 0, n){
		a[i] = _a[i];
	}
	For(i, 0, q){
		auto l = _l[i], r = _r[i];
		b[i] = query{l, r};
	}

	For(iq, 0, q){
		auto &[l, r] = b[iq];
		ForE(i, l, r){
			tans[i] = -a[i];
		}

		monotonic_stack st;
		ForE(i, l, r){
			st.insert(a[i]);
			tans[i] += st.sum;
		}
		st = monotonic_stack();
		FordE(i, r, l){
			st.insert(a[i]);
			tans[i] += st.sum;
		}
		ans[iq] = *min_element(tans + l, tans + r + 1);
	}
	return vector <ll>(ans, ans + q);
}

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