제출 #407086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407086		Antekb	Meetings (IOI18_meetings)	C++14	36 / 100	5527 ms	9028 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp(x, y) make_pair(x ,y)
using namespace std;
typedef long long ll;
const int N=1<<17;
int ans[N+N], pref[N+N], suf[N+N], siz[N+N];
pair<int, pair<int, int> > quer(int v, int L, int R, int l, int r){
	if(L==l && R==r){
		//cout<<L<<" "<<R<<" "<<ans[v]<<" "<<pref[v]<<" "<<suf[v]<<" "<<siz[v]<<"\n";
		return(mp(ans[v], mp(pref[v], suf[v])));
	}
	int M=(L+R)>>1;
	if(l<=M && M<r){
		pair<int, pair<int, int> > a=quer(2*v, L, M, l, M), b=quer(2*v+1, M+1, R, M+1, r);
		int x=max({a.st, b.st, a.nd.nd+b.nd.st});
		int y=a.nd.st;
		int z=b.nd.nd;
		if(M-l+1==a.st)y=b.nd.st+a.st;
		if(r-M==b.st)z=b.st+a.nd.nd;
		//cout<<L<<" "<<R<<" "<<l<<" "<<r<<" | "<<x<<" "<<y<<" "<<z<<"\n";
		return mp(x, mp(y, z));
	}
	else{
		if(l<=M)return quer(2*v, L, M, l, r);
		else return quer(2*v+1, M+1, R, l, r);
	}
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
 	int Q = L.size();
  	std::vector<long long> C(Q);
  	int n=H.size();
  	int M=0;
  	for(int i=0; i<n; i++)M=max(M, H[i]);
  	if(M<=2){
  	for(int i=0; i<n; i++){
  		ans[N+i]=pref[N+i]=suf[N+i]=(H[i]==1);
  		siz[N+i]=1;
  	}
  	for(int i=N-1; i>0; i--){
  		ans[i]=max({ans[2*i], ans[2*i+1], pref[2*i+1]+suf[2*i]});
  		pref[i]=pref[2*i];
  		if(ans[2*i]==siz[2*i])pref[i]=siz[2*i]+pref[2*i+1];
  		suf[i]=suf[2*i+1];
  		if(ans[2*i+1]==siz[2*i+1])suf[i]=siz[2*i]+suf[2*i];
  		siz[i]=siz[2*i]*2;
  	}
  	for(int j=0; j<Q; j++){
  		C[j]=(R[j]-L[j]+1)*2-quer(1, 0, N-1, L[j], R[j]).st;
  	}
  	}
  	else{
  	vector<long long> lew(n), pra(n);
  	for (int j = 0; j < Q; ++j) {
  		lew[L[j]]=H[L[j]];
  		stack<pair<int, int>> S;
  		ll ans=0;
  		for(int i=L[j]; i<=R[j]; i++){
  			int k=0;
  			while(S.size() && H[i]>S.top().st){
  				ans-=S.top().st*1ll*S.top().nd;
  				k+=S.top().nd;
  				S.pop();
  			}
  			k++;
  			ans+=H[i]*1ll*k;
  			S.push(mp(H[i], k));
  			lew[i]=ans;
  		}
  		ans=0;
  		while(S.size())S.pop();
  		for(int i=R[j]; i>=L[j]; i--){
  			int k=0;
  			while(S.size() && H[i]>S.top().st){
  				ans-=S.top().st*1ll*S.top().nd;
  				k+=S.top().nd;
  				S.pop();
  			}
  			k++;
  			ans+=H[i]*1ll*k;
  			S.push(mp(H[i], k));
  			pra[i]=ans;
  		}
  		ll res=1e18;
  		for(int i=L[j]; i<=R[j]; i++){
  			//cout<<i<<" "<<lew[i]<<" "<<pra[i]<<"\n";
  			res=min(res, lew[i]+pra[i]-H[i]);
  		}
  		C[j] = res;
  	}
  	}
  	return C;
}

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