Submission #898078

#	Time	Username	Problem	Language	Result	Execution time	Memory
898078		MuhammadSaram	Robots (IOI13_robots)	C++17	90 / 100	621 ms	65536 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

const int M = 5e4, inf=2e9+1;
int seg[M*4];

void modify(int p,int x,int v=1,int s=0,int e=M)
{
	if (s+1==e)
	{
		seg[v]=x;
		return;
	}
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	if (p<mid)
		modify(p,x,lc,s,mid);
	else
		modify(p,x,rc,mid,e);
	seg[v]=min(seg[lc],seg[rc]);
}

int get(int l,int r,int v=1,int s=0,int e=M)
{
	if (e<=l or r<=s)
		return inf;
	if (l<=s and e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v*2,rc=v*2+1;
	return min(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
	int mx=0,mx1=0;
	for (int i=0;i<a;i++)
		mx=max(mx,x[i]);
	for (int i=0;i<b;i++)
		mx1=max(mx1,y[i]);
	for (int i=0;i<t;i++)
		if (w[i]>=mx and s[i]>=mx1)
			return -1;
	if (b==0)
	{
		int cnt[a]={};
		sort(x,x+a);
		for (int i=0;i<t;i++)
		{
			int it=upper_bound(x,x+a,w[i])-x;
			cnt[it]++;
		}
		int ans=cnt[a-1],su=cnt[a-1];
		for (int i=a-2;i>=0;i--)
		{
			int oops=min(cnt[i],ans*(a-i)-su);
			cnt[i]-=oops;
			su+=oops;
			ans+=(cnt[i]+a-i-1)/(a-i);
			su+=cnt[i];
		}
		return ans;
	}
	map<int,vector<int>> cnt;
	vector<int> dsz;
	for (int i=0;i<t;i++)
	{
		if (cnt.find(s[i])==cnt.end())
			dsz.push_back(s[i]);
		cnt[s[i]].push_back(w[i]);
	}
	int pre[1+(int)dsz.size()]={};
	sort(dsz.begin(),dsz.end());
	reverse(dsz.begin(),dsz.end());
	int ind=0;
	for (int i=0;i<dsz.size();i++)
	{
		for (int j:cnt[dsz[i]])
			modify(ind++,j);
		pre[i+1]=pre[i]+(int)cnt[dsz[i]].size();
	}
	sort(x,x+a);
	sort(y,y+b);
	int stt=0,e=t;
	while (stt+1<e)
	{
		int mid=(stt+e)/2;
		multiset<int> msz;
		for (int i=0;i<t;i++)
			msz.insert(s[i]);
		ind=0;
		for (int i=0;i<dsz.size();i++)
			for (int j:cnt[dsz[i]])
				modify(ind++,j);
		for (int i=0;i<a;i++)
		{
			for (int j=0;j<mid;j++)
			{
				if (get(0,ind)>=x[i])
					break;
				int st=-1,en=ind-1;
				while (st+1<en)
				{
					int mid1=(st+en)/2;
					if (get(0,mid1+1)<x[i])
						en=mid1;
					else
						st=mid1;
				}
				modify(en,inf);
				int it=upper_bound(pre,pre+1+(int)dsz.size(),en)-pre;
				msz.erase(msz.find(dsz[it-1]));
			}
		}
		for (int i=0;i<b;i++)
			for (int j=0;j<mid;j++)
			{
				auto it=msz.lower_bound(y[i]);
				if (it!=msz.begin())
				{
					it--;
					msz.erase(it);
				}
				else
					break;
			}
		if (msz.empty())
			e=mid;
		else
			stt=mid;
	}
	return e;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i=0;i<dsz.size();i++)
      |               ~^~~~~~~~~~~
robots.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int i=0;i<dsz.size();i++)
      |                ~^~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10