Submission #137843

#	Time	Username	Problem	Language	Result	Execution time	Memory
137843		bensonlzl	Meetings (IOI18_meetings)	C++14	0 / 100	3 ms	504 KiB

meetings

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,pi> pii;

ll N, Q;

ll mount[1000005];

struct node{
	node *left = nullptr, *right = nullptr;
	int S, E, pre1 = 0, suff1 = 0, seg1 = 0;
	node(int _s, int _e){
		S = _s;
		E = _e;
		if (S == E){
			pre1 = suff1 = seg1 = (mount[S] == 1);
			return;
		}
		left = new node(S,(S+E)/2);
		right = new node((S+E)/2+1,E);
		if (left->pre1 == left->E - left->S + 1){
			pre1 = left->pre1 + right->pre1;
		}
		else pre1 = left->pre1;
		if (right->suff1 == right->E - right->S + 1){
			suff1 = right->suff1 + right->suff1;
		}
		else suff1 = right->suff1;
		seg1 = max(left->seg1,right->seg1);
		seg1 = max(seg1,left->suff1 + right->pre1);
	}
	pii query(int l, int r){
		if (l > E || r < S || r < l) return pii(0,pi(0,0));
		if (l <= S && E <= r) return pii(seg1,pi(pre1,suff1));
		pii l1 = left->query(l,min(r,(S+E)/2)), r1 = right->query(max((S+E)/2+1,l),r);
		int sg = max(max(l1.first,r1.first),l1.second.second+r1.second.first);
		int pr, su;
		if (l1.second.first == max(0,left->E-l+1)){
			pr = l1.second.first + r1.second.first;
		}
		else pr = l1.second.first;
		if (r1.second.second == max(0,r-right->S+1)){
			su = r1.second.second + l1.second.second;
		}
		else su = r1.second.second;
		return pii(sg,pi(pr,su));
	}
} *root;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	vector<ll> ans;
	N = H.size();
	Q = L.size();
	for (int i = 0; i < N; ++i){
		mount[i] = H[i];
	}
	if (N <= 5000){
		for (int i = 0; i < Q; ++i){
			ll maxi = 0;
			vector<ll> pos;
			pos.resize(R[i]-L[i]+1,0);
			for (ll j = L[i]; j <= R[i]; ++j){
				maxi = max(maxi,mount[j]);
				pos[j-L[i]] += (j-L[i]+1)*maxi;
			}
			maxi = 0;
			for (ll j = R[i]; j >= L[i]; --j){
				maxi = max(maxi,mount[j]);
				pos[j-L[i]] += (R[i]-j+1)*maxi;
			}
			ll mini = 1e17;
			for (int j = 0; j < R[i]-L[i]+1; ++j){
				mini = min(mini,pos[j]);
			}
			ans[i] = mini;
		}
		return ans;
	}
	else{
		root = new node(0,N-1);
		for (int i = 0; i < Q; ++i){
			ans.push_back(2*(R[i]-L[i]+1)-root->query(L[i],R[i]).first);
		}
		return ans;
	}
}

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