제출 #286676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286676		AlanChen	모임들 (IOI18_meetings)	C++14	19 / 100	5562 ms	9464 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;

typedef v<int> vi;
typedef long long ll;

#define sz(S) (int)(S).size()
#define pb push_back
#define rsz resize
#define f first
#define s second
#define mp make_pair

#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)


#define trv(x,S) for(auto& x:(S))

template<class A,class B> bool ckmax(A& a1,const B& b1) {return a1<b1?a1=b1,1:0;}
template<class A,class B> bool ckmin(A& a1,const B& b1) {return a1>b1?a1=b1,1:0;}

const int mx=1000000;
int q;
v<ll> ans;
ll pcost1[mx];
ll pcost2[mx];

void getcost(const v<ll>& H,int l,int r,ll rst[])
{

	v<pair<ll,int>> stps;

	ll ccost=0;
	lp(i,l,r+1)
	{
		stps.pb(mp(H[i],1)); ccost+=H[i];
		while(sz(stps)>1&&stps[sz(stps)-1].f>=stps[sz(stps)-2].f)
		{
			ccost+=(stps[sz(stps)-1].f-stps[sz(stps)-2].f)*stps[sz(stps)-2].s;
			stps[sz(stps)-2].f=stps[sz(stps)-1].f;
			stps[sz(stps)-2].s+=stps[sz(stps)-1].s;
			stps.pop_back();
		}
		rst[i]=ccost;
	}
}

v<ll> minimum_costs(vi H, vi L,vi R)
{
	q=sz(L);
	v<ll> hl(sz(H)),hlr(sz(H));
	vi Lr(q),Rr(q);
	lp(i,sz(H)) hl[i]=H[i];
	lp(i,sz(H)) hlr[i]=H[sz(H)-1-i];
	lp(i,q) Lr[i]=sz(H)-1-L[i];
	lp(i,q) Rr[i]=sz(H)-1-R[i];
	lp(i,q) swap(Lr[i],Rr[i]);


	ans.rsz(q);
	trv(x,ans) x=1ll<<60;

	lp(qn,q)
	{
		getcost(hl,L[qn],R[qn],pcost1);
		getcost(hlr,Lr[qn],Rr[qn],pcost2);
		lp(i,L[qn],R[qn]+1) ckmin(ans[qn],pcost1[i]+pcost2[sz(H)-1-i]-H[i]);

	}



	return ans;
}

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