Submission #1199031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199031		alind	Meetings (IOI18_meetings)	C++20	4 / 100	5590 ms	2620 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, 0), sm(4*sz, 0) {};
	void prop(int i, int l, int r) {
		if (!lzy[i]) 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] = 0;
	}
	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); }
	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); }
	ll que() {return que(0, n); }
};

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	int Q = L.size();
	std::vector<long long> C(Q);
	for (int j = 0; j < Q; ++j) {
		int d = R[j] - L[j] + 1;
		SegTree a(d), b(d);
		vector<ll> pref(d), suf(d);
		vector<pair<int, int>> stk; stk.push_back({1<<30, -1});
		for (int i = 0; i < d; i++) {
			const int x = L[j] + i;
			while (stk.back().first <= H[x]) stk.pop_back();
			a.set(stk.back().second+1, i + 1, H[x]);
			pref[i] = a.que();
			stk.push_back({H[x], i});
		}
		stk.clear(); stk.push_back({1<<30, d});
		for (int i = d-1; ~i; i--) {
			const int x = L[j] + i;
			while (stk.back().first <= H[x]) stk.pop_back();
			b.set(i, stk.back().second, H[x]);
			suf[i] = b.que();
			stk.push_back({H[x], i});
		}
		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