Submission #300777

#	Time	Username	Problem	Language	Result	Execution time	Memory
300777		TMJN	Meetings (IOI18_meetings)	C++17	0 / 100	33 ms	2304 KiB

meetings

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

int N,Q,L[100000],R[100000],tree[1<<18];

int calc(int l,int r){
	int a=0;
	l+=1<<17;
	r+=1<<17;
	while(l<=r){
		a=max({a,tree[l],tree[r]});
		l=(l+1)/2;
		r=(r-1)/2;
	}
	return a;
}

vector<long long> minimum_costs(vector<int>H,vector<int>QL,vector<int>QR){
	N=H.size();
	Q=QL.size();
	for(int i=1;i<N;i++){
		if(H[i-1]==1&&H[i]==1){
			L[i]=L[i-1];
		}
		else{
			L[i]=i;
		}
	}
	R[N-1]=N-1;
	for(int i=N-2;i>=0;i--){
		if(H[i]==1&&H[i+1]==1){
			R[i]=R[i+1];
		}
		else{
			R[i]=i;
		}
	}
	for(int i=0;i<N;i++){
		if(H[i]==1){
			tree[i+(1<<17)]=R[i]-L[i]+1;
		}
	}
	for(int i=(1<<17)-1;i;i--){
		tree[i]=max(tree[i+i],tree[i+i+1]);
	}
	vector<long long>res(Q);
	for(int _=0;_<Q;_++){
		int t=0;
		int l,r;
		if(H[QL[_]]==1){
			t=max(t,R[QL[_]]-QL[_]+1);
			l=R[QL[_]]+1;
		}
		else{
			l=QL[_];
		}
		if(H[QR[_]]==1){
			t=max(t,QR[_]-L[QL[_]]+1);
			r=L[QR[_]]-1;
		}
		else{
			r=QR[_];
		}
		t=max(t,calc(l,r));
		res[_]=2*(QR[_]-QL[_]+1)-t;
	}
	return res;
}

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