Submission #130456

#	Time	Username	Problem	Language	Result	Execution time	Memory
130456		rondojim	Meetings (IOI18_meetings)	C++17	41 / 100	508 ms	126004 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 750005;
const int maxv = 25;
int arr[maxn];
 
int n, q;
 
vector<int> buck[maxv];
 
struct segtree
{
	int sz;
	struct node
	{
		ll val;
		node *left, *right;
		node(ll _val = 0, node* _left = NULL, node* _right = NULL)
		{
			val = _val; left = _left; right = _right;
		}
		node* build(vector<ll> &vals, int L, int R)
		{
			if(L == R)
			{
				return new node(vals[L], NULL, NULL);
			}
			int M = (L+R)/2;
			node* x = build(vals, L, M);
			node* y = build(vals, M+1, R);
			return new node(min(x->val, y->val), x, y);
		}
		ll ask(int i, int j, int L, int R)
		{
			if(i> R || j< L) return 4e18;
			if(i<= L && R<= j) return val;
			int M = (L+R)/2;
			ll x = left->ask(i, j, L, M);
			ll y = right->ask(i, j, M+1, R);
			return min(x, y);
		}
	};
	node *root;
	segtree(){}
	segtree(vector<ll> &vals)
	{
		sz = vals.size();
		root = root->build(vals, 0, sz-1);
	}
 
	ll ask(int i, int j)
	{
		return root->ask(i, j, 0, sz-1);
	}
};
 
struct cart
{
	ll val;
	vector<cart*> ptr; //size k+1
	vector<int> poles; //size k
	vector<ll> cand; //size k+1 
	segtree seg;
	cart(){}
	cart(int L, int R, int H)
	{
		if(L> R)
		{
			val = 0;
			return;
		}
		int lo = lower_bound(buck[H].begin(), buck[H].end(), L)-buck[H].begin();
		int hi = upper_bound(buck[H].begin(), buck[H].end(), R)-buck[H].begin()-1;
		for(int i = lo; i<= hi; i++)
		{
			poles.pb(buck[H][i]);
		}
		ptr.resize(poles.size()+1);
		cand.resize(poles.size()+1);
		for(int i = 0; i< (int) ptr.size(); i++)
		{
			int sai = (i?poles[i-1]+1:L);
			int kwa = (i< poles.size()?poles[i]-1:R);
			// printf("[%d %d] %d (%d)to [%d %d] %d\n", L, R, H, i, sai, kwa, H-1);
			ptr[i] = new cart(sai, kwa, H-1);
			cand[i] = ptr[i]->val;
			cand[i] -= 1LL*(kwa-sai+1)*H;
		}
		seg = segtree(cand);
		val = min(seg.ask(0, seg.sz-1)+1LL*(R-L+1)*H, 1LL*(R-L+1)*H);
		// printf("[%d %d] %d = %lld\n", L, R, H, val);
	}
 
	ll ask(int i, int j, int L = 0, int R = n-1, int H = 21)
	{
		if(L> R|| i> R || j< L) return 0;
		// printf("asking %d %d %d\n", L, R, H);
		if(i<= L && R<= j)
		{
			// printf("= %lld\n", val);
			return val;
		}
		int sai = lower_bound(poles.begin(), poles.end(), i)-poles.begin();
		int kwa = upper_bound(poles.begin(), poles.end(), j)-poles.begin()-1;
		if(sai> kwa)
		{
			int tahm = (sai?poles[sai-1]+1:L);
			int kench = (sai< poles.size()?poles[sai]-1:R);
			return ptr[sai]->ask(i, j, tahm, kench, H-1); 	
		}
		// if(sai == kwa) printf("sai = kwa! [%d]\n", poles[sai]);
		// printf("for [%d %d]\n", L, R);
		ll x = ptr[sai]->ask(i, poles[sai]-1, sai?poles[sai-1]+1:L, poles[sai]-1, H-1)-1LL*(poles[sai]-i)*H;
		// printf("x = %lld\n", x);
		ll mid = seg.ask(sai+1, kwa);
		ll y = ptr[kwa+1]->ask(poles[kwa]+1, j, poles[kwa]+1, kwa+1<poles.size()?poles[kwa+1]-1:R, H-1)-1LL*(j-poles[kwa])*H;
		// printf("y = %lld\n", y);
		return min(min(0LL, mid), min(x, y)) + 1LL*(j-i+1)*H;
	}
};
 
cart foo;
 
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	n = H.size(); q = L.size();
	for(int i = 0; i< n; i++) arr[i] = H[i];
	for(int i = 0; i< n; i++)
	{
		buck[arr[i]].pb(i);
	}
	foo = cart(0, n-1, 21);
	vector<ll> ans(q);
	for(int i = 0; i< q; i++)
	{
		ans[i] = foo.ask(L[i], R[i]);
		assert(ans[i]> 0);
	}
	return ans;
}

Compilation message (stderr)

meetings.cpp: In constructor 'cart::cart(int, int, int)':
meetings.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    int kwa = (i< poles.size()?poles[i]-1:R);
               ~^~~~~~~~~~~~~~
meetings.cpp: In member function 'll cart::ask(int, int, int, int, int)':
meetings.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    int kench = (sai< poles.size()?poles[sai]-1:R);
                 ~~~^~~~~~~~~~~~~~
meetings.cpp:123:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   ll y = ptr[kwa+1]->ask(poles[kwa]+1, j, poles[kwa]+1, kwa+1<poles.size()?poles[kwa+1]-1:R, H-1)-1LL*(j-poles[kwa])*H;
                                                         ~~~~~^~~~~~~~~~~~~

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