제출 #132165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132165		amiratou	모임들 (IOI18_meetings)	C++14	17 / 100	162 ms	7388 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF LLONG_MAX
int st[400002],st2[400002],st3[400002];
vector<int> A,tab;
void build(int node,int l,int r){
	if(l==r){
		st[node]=l;
		st3[node]=tab[l];
		return ;
	}
	int med=(l+r)/2;
	build(node*2,l,med),build(node*2+1,med+1,r);
	if(A[st[node*2+1]]>=A[st[node*2]])st[node]=st[node*2+1];
	else st[node]=st[node*2];
	st3[node]=max(st3[node*2],st3[node*2+1]);
}
void build2(int node,int l,int r){
	if(l==r){
		st2[node]=l;
		return ;
	}
	int med=(l+r)/2;
	build2(node*2,l,med),build2(node*2+1,med+1,r);
	if(A[st2[node*2]]>=A[st2[node*2+1]])st2[node]=st2[node*2];
	else st2[node]=st2[node*2+1];
}
int query(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return -1;
	if(l>=i&&r<=j){
		if(A[st[node]]<2)return -1;
		return st[node];
	}
	int med=(l+r)/2;
	int idx=query(node*2+1,med+1,r,i,j);
	if(idx!=-1)return idx;
	return query(node*2,l,med,i,j);
}
int query2(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return -1;
	if(l>=i&&r<=j){
		if(A[st2[node]]<2)return -1;
		return st2[node];
	}
	int med=(l+r)/2;
	int idx=query2(node*2,l,med,i,j);
	if(idx!=-1)return idx;
	return query2(node*2+1,med+1,r,i,j);
}
int query3(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return -1;
	if(l>=i&&r<=j)
		return st3[node];
	int med=(l+r)/2;
	return max(query3(node*2,l,med,i,j),query3(node*2+1,med+1,r,i,j));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
	int n=H.size();
	A=H;
	tab.resize(n);
	int prev=n-1;
	for (int i = n-1; i >=0 ; i--)
	{
		if(H[i]==1)tab[i]=-1;
		else{
			tab[i]=prev-i-((H[prev]==2)?1:0);
			prev=i;
		}
	}
	build(1,0,n-1);
	build2(1,0,n-1);
	int Q = L.size();
	vector<ll> C(Q);
	for (int q = 0; q < Q; ++q) {
		int lefty=query2(1,0,n-1,L[q],R[q]),righty=query(1,0,n-1,L[q],R[q]);
		//cerr<<lefty<<" "<<righty<<"\n";
		if(lefty==-1){
			C[q]=R[q]-L[q]+1;
			continue;
		}
		C[q]=INF;
		if(abs(lefty-righty)<=1)C[q]=min(C[q],(ll)(2*(R[q]-L[q]+1)));
		else {
			int nb=query3(1,0,n-1,lefty,righty-1);
			C[q]=min(C[q],(ll)(nb+2*(R[q]-L[q]+1-nb)));

		}
		if(righty!=R[q]){
			righty++;
			C[q]=min(C[q],(ll)(R[q]-righty+1+2*(righty-L[q])));
		}
		if(lefty!=L[q]){
			lefty--;
			C[q]=min(C[q],(ll)((lefty-L[q])+1+2*(R[q]-lefty)));
		}
	}
	return C;
}

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