Submission #830857

#	Time	Username	Problem	Language	Result	Execution time	Memory
830857		tranxuanbach	Meetings (IOI18_meetings)	C++17	19 / 100	428 ms	2900 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;
};

const int N = 750'000 + 5;

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

ll ans[N];

namespace subtask12{
	bool check(){
		return n <= 5000 and q <= 5000;
	}

	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;
		}
	};

	ll tans[N];

	vector <ll> solve(){
		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);
	}
}

namespace subtask3{
	bool check(){
		return n <= 100'000 and *max_element(a, a + n) <= 2;
	}

	const int N = 1e5 + 5, LN = 17;

	vector <int> pos2;
	int delta[N];
	int sptb[LN][N];

	int query(int l, int r){
		int j = __lg(r - l + 1);
		return max(sptb[j][l], sptb[j][r - (1 << j) + 1]);
	}

	vector <ll> solve(){
		pos2.emplace_back(-1);
		For(i, 0, n){
			if (a[i] == 2){
				pos2.emplace_back(i);
			}
		}
		pos2.emplace_back(n);
		For(i, 0, n){
			if (a[i] == 2){
				delta[i] = 0;
			}
			else{
				auto itr = --upper_bound(pos2.begin(), pos2.end(), i);
				delta[i] += i - *itr;
				itr++;
				delta[i] += *itr - i;
			}
		}

		For(i, 0, n){
			sptb[0][i] = delta[i];
		}
		For(j, 1, LN){
			ForE(i, 0, n - (1 << j)){
				sptb[j][i] = max(sptb[j - 1][i], sptb[j - 1][i + (1 << (j - 1))]);
			}
		}

		For(iq, 0, q){
			auto &[l, r] = b[iq];
			auto tl = *lower_bound(pos2.begin(), pos2.end(), l);
			auto tr = *(--upper_bound(pos2.begin(), pos2.end(), r));
			if (tl > r){
				ans[iq] = r - l + 1;
				continue;
			}
			ans[iq] = 2 * (r - l + 1) - max({tl - l, r - tr, query(tl, tr)});
		}
		return vector <ll>(ans, ans + q);
	}
}

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};
	}

	if (subtask12::check()){
		return subtask12::solve();
	}
	if (subtask3::check()){
		return subtask3::solve();
	}
	return {};
}

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