Submission #296579

#	Time	Username	Problem	Language	Result	Execution time	Memory
296579		nvmdava	Meetings (IOI18_meetings)	C++17	0 / 100	28 ms	2816 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
vector<long long> ans;

const int N = 1000000;
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<pair<int, ll> > tmp;
int n;
ll h[N];
vector<int> wr;

struct Mina{
	int ri[N], ne[N];
	ll c[N], h[N];

	void build(){

		tmp.push_back({0, 0});
		h[0] = INF;
		for(int i = 1; i <= n; ++i){
			h[i] = ::h[i];
			int id;
			ll hh, s = INF;
			while((hh = h[id = tmp.back().ff]) < h[i]){
				s = min(s, tmp.back().ss + (i - id) * hh);
				c[id] = s;
				ri[id] = i;
				tmp.pop_back();
				s += (id - tmp.back().ff - 1) * hh + h[tmp.back().ff];
			}
			tmp.back().ss = s;
			tmp.push_back({i, 0});
		}
		while(!tmp.empty()){
			c[tmp.back().ff] = 0;
			ri[tmp.back().ff] = n + 1;
			tmp.pop_back();
		}
		ne[n] = n + 1;
		for(int i = n - 1; i > 0; --i){
			ne[i] = ne[i + 1];
			if(h[i] != h[i + 1])
				ne[i] = i + 1;
		}
	}

	ll query(int l, int r){
		if(ne[l] > r)
			return (r - l + 1) * h[l];
		if(ri[l] > r)
			return query(ne[l], r) + (ne[l] - l) * h[l];
		wr.clear();
		ll s = 0;
		ll mn;
		int t = l;
		while(ri[t] <= r){
			s += (ri[t] - t) * h[t];
			wr.push_back(t);
			t = ri[t];
		}
		s += (r + 1 - t) * h[t];
		mn = s;
		for(auto& x : wr){
			mn = min(mn, s - (ri[x] - x) * h[x] + c[x]);
			s += (ri[x] - x) * (h[ri[x]] - h[x]);
		}
		return mn;
	}
} le, ri;

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


	n = H.size();
	for(int i = 1; i <= n; ++i)
		h[i] = H[i - 1];
	h[0] = INF;

	le.build();
	reverse(h + 1, h + n + 1);
	ri.build();

	int q = L.size();
	ans.resize(q);

	for(int i = 0; i < q; ++i)
		ans[i] = min(le.query(1 + L[i], 1 + R[i]), ri.query(n - R[i], n - L[i]));

	return ans;
}

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