Submission #257931

#	Time	Username	Problem	Language	Result	Execution time	Memory
257931		ChrisT	Robots (IOI13_robots)	C++17	100 / 100	1813 ms	24676 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 1e6 + 5, LOG = 18, MOD = 1e9 + 7;
int putaway (int a, int b, int t, int *x, int *y, int *w, int *s) { //2 segtree + bsearch
	sort(x,x+a); sort(y,y+b);
	vector<pii> v(t);
	for (int i = 0; i < t; i++) v[i] = {w[i],s[i]};
	sort(v.begin(),v.end());
	auto check = [&] (int mid) -> bool {
		priority_queue<int> ys;
		int vp = 0;
		for (int i = 0; i < a; i++) {
			while (vp < t && v[vp].first < x[i]) ys.push(v[vp++].second);
			for (int j = 0; j < mid && !ys.empty(); j++) ys.pop();
		}
		while (vp < t) ys.push(v[vp++].second);
		for (int i = b-1; i >= 0; i--) {
			if (!ys.empty() && ys.top() >= y[i]) return 0;
			for (int j = 0; j < mid && !ys.empty(); j++) ys.pop();
		}
		return ys.empty();
	};
	int low = 1, high = t, ans = -1, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (check(mid)) high = (ans = mid) - 1;
		else low = mid + 1;
	}
	return ans;
}

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