Submission #550345

#	Time	Username	Problem	Language	Result	Execution time	Memory
550345		Hanksburger	Robots (IOI13_robots)	C++17	100 / 100	689 ms	10860 KiB

robots

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