Submission #140412

#	Time	Username	Problem	Language	Result	Execution time	Memory
140412		arthurconmy	Meetings (IOI18_meetings)	C++14	4 / 100	2278 ms	392144 KiB

meetings

#include <bits/stdc++.h>

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

using namespace std;
using ll = long long;

const int p2 = 4096;
const int MAXN = 3000;

int max_segtree[p2+p2];
ll sum_segtree[MAXN][p2+p2];

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,max_segtree[l++]);
		if(r%2 == 0) ans=max(ans,max_segtree[r--]);

		l/=2;
		r/=2;
	}

	return ans;
}

ll query(int tree, int l, int r)
{
	l += p2;
	r += p2;

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

	ll ans=0;

	while(l<=r)
	{
		if(l%2 == 1) ans+=sum_segtree[tree][l++];
		if(r%2 == 0) ans+=sum_segtree[tree][r--];

		l/=2;
		r/=2;
	}

	return ans;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) 
{
  // int Q = L.size();
  // std::vector<long long> C(Q);
  // for (int j = 0; j < Q; ++j) {
  //   C[j] = H[L[j]];
  // }
  // return C;

	int q = L.size();
	int n = H.size();

	for(int i=0; i<n; i++)
	{
		max_segtree[i+p2]=H[i];
	}

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

	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			sum_segtree[i][j+p2]=ll(RMQ(i,j));
		}
	}

	for(int i=0; i<n; i++)
	{
		for(int j=p2-1; j>=1; j--)
		{
			sum_segtree[i][j] = sum_segtree[i][j+j] + sum_segtree[i][j+j+1];
		}
	}

	vector<ll> ans;

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

		for(int j=L[i]; j<=R[i]; j++)
		{
			cur = min(cur, query(j,L[i],R[i]));
			//cout << i << " " << j << " " << query(i,L[i],R[i]) << endl;
		}

		ans.push_back(cur);
	}

	return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		for(auto e:minimum_costs({2,4,3,5},{0,1},{2,3}))
		{
			cout << e << endl;
		}
	}
#endif

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