oj.uz

Submission #296579

# Submission time Handle Problem Language Result Execution time Memory
296579 2020-09-10T16:36:51 Z nvmdava Meetings (IOI18_meetings) C++17
0 / 100
 28 ms 2816 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 28 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 28 ms 2816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -