Submission #1199038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199038		alind	Meetings (IOI18_meetings)	C++20	4 / 100	5594 ms	2180 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct SegTree{
	int n;
	vector<int> lzy;
	vector<ll> sm;
	SegTree(int sz) : n(sz), lzy(4*sz, -1), sm(4*sz, 0) {};
	void prop(int i, int l, int r) {
		if (lzy[i] == -1) return;
		sm[i] = 1ll * (r - l) * lzy[i];
		if (r - l <= 1) return;
		lzy[i * 2 + 1] = lzy[i * 2 + 2] = lzy[i];
		lzy[i] = -1;
	}
	void set(int i, int l, int r, int a, int b, int val) {
		prop(i, l, r);
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) {
			lzy[i] = val;
			prop(i, l, r);
			return;
		}
		int m = (l+r)>>1;
		set(i * 2 + 1, l, m, a, b, val);
		set(i * 2 + 2, m, r, a, b, val);
		sm[i] = sm[i * 2 + 1] + sm[i * 2 + 2];
	}
	void set(int a, int b, int val) { set(0, 0, n, a, b, val); }
	void clear() { set(0, n, 0); }
	ll que(int i, int l, int r, int a, int b) {
		prop(i, l, r);
		if (b <= l || r <= a) return 0;
		if (a <= l && r <= b) return sm[i];
		int m = (l+r)>>1;
		return que(i * 2 + 1, l, m, a, b) + que(i * 2 + 2, m, r, a, b);
	}
	ll que(int a, int b) { return que(0, 0, n, a, b); }
};

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	int N = H.size();
	int Q = L.size();
	std::vector<long long> C(Q);
	SegTree st(N);
	for (int j = 0; j < Q; ++j) {
		int d = R[j] - L[j] + 1;
		vector<ll> pref(d), suf(d);
		vector<pair<int, int>> stk; stk.push_back({1<<30, L[j]-1});
		st.clear();
		for (int i = 0; i < d; i++) {
			const int x = L[j] + i;
			while (stk.back().first <= H[x]) stk.pop_back();
			st.set(stk.back().second+1, x + 1, H[x]);
			pref[i] = st.que(0, x+1);
			stk.push_back({H[x], x});
		}
		st.clear();
		stk.clear(); stk.push_back({1<<30, R[j]+1});
		for (int i = d-1; ~i; i--) {
			const int x = L[j] + i;
			while (stk.back().first <= H[x]) stk.pop_back();
			st.set(x, stk.back().second, H[x]);
			suf[i] = st.que(x, N);
			stk.push_back({H[x], x});
		}
		ll mn = 1ll<<62;
		for (int i = 0; i < d; i++)
			mn = min(mn, pref[i] + (i < d - 1 ? suf[i+1] : 0));
		C[j] = mn;
	}
	return C;
}

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