Submission #550344

#	Time	Username	Problem	Language	Result	Execution time	Memory
550344		Hanksburger	Robots (IOI13_robots)	C++17	100 / 100	695 ms	28348 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> toy[1000005];
priority_queue<long long> pq;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	sort(X, X+A);
	sort(Y, Y+B);
	for (long long i=0; i<T; i++)
    {
    	long long ind=upper_bound(X, X+A, W[i])-X, jnd=upper_bound(Y, Y+B, S[i])-Y;
    	if (ind==A && jnd==B)
    		return -1;
    	toy[i]={ind, jnd};
	}
	sort(toy, toy+T);
    long long l=1, r=T;
    while (l<r)
    {
    	long long mid=(l+r)/2, ind=0;
    	while (!pq.empty())
    		pq.pop();
    	for (long long i=0; i<A; i++)
    	{
    		while (ind<T && toy[ind].first<=i)
    		{
    			pq.push(toy[ind].second);
    			ind++;
			}
    		long long cnt=mid;
    		while (!pq.empty() && cnt)
    		{
    			pq.pop();
    			cnt--;
			}
		}
		while (ind<T)
		{
			pq.push(toy[ind].second);
			ind++;
		}
		for (long long i=B-1; i>=0; i--)
		{
			if (pq.empty() || pq.top()>i)
				break;
			long long cnt=mid;
			while (!pq.empty() && cnt)
			{
				pq.pop();
				cnt--;
			}
		}
		if (pq.empty())
			r=mid;
		else
			l=mid+1;
	}
	return l;
}

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