제출 #137851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137851		bensonlzl	Meetings (IOI18_meetings)	C++14	19 / 100	1002 ms	2604 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;
typedef pair<ll,ll> pl;

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);
		seg1 = max(seg1,max(pre1,suff1));
	}
	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;
		sg = max(sg,max(pr,su));
		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){
			vector<ll> pos;
			pos.resize(R[i]-L[i]+1,0);
			
			vector<pl> mv;
			ll sum = 0;
			for (int j = 0; j < R[i]-L[i]+1; ++j){
				ll cur = 1;
				while (!mv.empty() && mv.back().first < mount[j+L[i]]){
					cur += mv.back().second;
					sum -= mv.back().second * mv.back().first;
					mv.pop_back();
				}
				mv.push_back(pl(mount[j+L[i]],cur));
				sum += mount[j+L[i]]*cur;
				pos[j] += sum;
			}
			mv.clear();
			sum = 0;
			for (int j = R[i]-L[i]; j >= 0; --j){
				ll cur = 1;
				while (!mv.empty() && mv.back().first < mount[j+L[i]]){
					cur += mv.back().second;
					sum -= mv.back().second * mv.back().first;
					mv.pop_back();
				}
				mv.push_back(pl(mount[j+L[i]],cur));
				sum += mount[j+L[i]]*cur;
				pos[j] += sum;
			}

			ll mini = 1e17;
			for (int j = 0; j < R[i]-L[i]+1; ++j){
				mini = min(mini,pos[j]-mount[j+L[i]]);
			}
			ans.push_back(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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40