Submission #140415

#	Time	Username	Problem	Language	Result	Execution time	Memory
140415		arthurconmy	Meetings (IOI18_meetings)	C++14	17 / 100	84 ms	7548 KiB

meetings

#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "meetings.h"
#endif

using namespace std;
using ll = long long;

const int p2 = 131072;
const int MAXN = 100000;

int st[p2+p2];
int one_start[MAXN];
int one_end[MAXN];

int RMQ(int l, int r)
{
	l += p2;
	r += p2;

	// if(l>r) swap(l,r);

	int ans=0;

	while(l<=r)
	{
		if(l%2 == 1) ans=max(ans,st[l++]);
		if(r%2 == 0) ans=max(ans,st[r--]);

		l/=2;
		r/=2;
	}

	return ans;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) 
{
	int n = H.size();
	int q = L.size();

	// compute one_start[i]

	int cur_start = 0;
	bool in_seg = 0;

	for(int i=0; i<n; i++)
	{
		if(H[i]!=1)
		{
			one_start[i]=-1;
			in_seg=0;
			continue;
		}

		if(!in_seg)
		{
			in_seg=1;
			cur_start=i;
			one_start[i]=i;
		}

		else
		{
			one_start[i]=cur_start;
		}
	}

	int cur_end = 0;
	in_seg = 0;

	for(int i=n-1; i>=0; i--)
	{
		if(H[i]!=1)
		{
			one_end[i]=-1;
			in_seg=0;
			continue;
		}

		if(!in_seg)
		{
			in_seg=1;
			cur_end=i;
			one_end[i]=i;
		}

		else
		{
			one_end[i]=cur_end;
		}
	}

	//for(int i=0; i<n; i++) cout << one_start[i] << " ";
	//cout << endl;

	for(int i=0; i<n; i++)
	{
		if(one_start[i]!=-1)
		{
			st[p2+i]=one_end[i]-one_start[i]+1;
		}
	}

	for(int i=p2-1; i>=1; i--)
	{
		st[i]=max(st[i+i],st[i+i+1]);
	}

	vector<ll> ans;

	for(int i=0; i<q; i++)
	{
		int cur=0;

		if(one_end[L[i]] != -1) cur = max(cur, min(R[i],one_end[L[i]])-L[i]+1);
		
		//if(i>0) cout << cur << endl;

		if(one_end[R[i]] != -1) cur = max(cur, R[i]-max(L[i],one_start[R[i]])+1);

		//if(i>0) cout << cur << endl;
	
		int left, right;

		if(one_end[L[i]]!=-1) left = one_end[L[i]]+1;
		else left = L[i];

		if(one_end[R[i]]!=-1) right = one_start[R[i]]-1;
		else right = R[i];

		cur = max(cur,RMQ(left,right));

		//if(i>0) cout << cur << endl;

		// cout << cur << endl;

		//cout << 2*(R[i]-L[i]+1) <<" "<< cur << endl;

		ans.push_back(2*(R[i]-L[i]+1) - cur);
	}

	return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		// cout << pow(2,17) << endl;

		minimum_costs({1,1,2,1},{0,1},{2,3});
	}
#endif

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