Submission #676450

#	Time	Username	Problem	Language	Result	Execution time	Memory
676450		penguin133	Robots (IOI13_robots)	C++17	100 / 100	1466 ms	26300 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

pi R[1000005], R2[1000005];
int vis[1000005];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	for(int i=1;i<=T;i++)R[i] = {W[i-1], S[i-1]};
	sort(X, X+A);
	sort(Y, Y+B);
	for(int i=0;i<T;i++){
		if(W[i] >= X[A-1] && S[i] >= Y[B-1])return -1;
	}
	int lo = 0, hi = T, ans = hi;
	sort(R+1, R+T+1);
	int in;
	while(lo <= hi){
		int m = (lo + hi)/2;
		for(int i=1;i<=T;i++)vis[i] = 0;
		in = 1;
		priority_queue<int>pq;
		for(int i=0;i<A;i++){
			while(in <= T && R[in].fi < X[i])pq.push(R[in].se), in++;
			for(int j=0;j<m;j++){
				if(pq.empty())break;
				pq.pop();
			}
		}
		while(in <= T)pq.push(R[in].se), in++;
		bool f = 1;
		for(int i=B-1;i>=0;i--){
			if(!pq.empty() && pq.top() >= Y[i])f = 0;
			for(int j=0;j<m;j++){
				if(pq.empty())break;
				pq.pop();
			}
		}
		if(pq.empty() && f)ans = m, hi = m - 1;
		else lo = m + 1;
	}
	return ans;
}

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