Submission #171087

#	Time	Username	Problem	Language	Result	Execution time	Memory
171087		dennisstar	Robots (IOI13_robots)	C++11	90 / 100	3050 ms	29764 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

vim cp1, cp2;
vector<pii> ar;
set<pii> S1, S2;
int cn1[50010], cn2[50010];

/*struct segTree {
	int seg[(1<<18)];
	void init() {memset(seg, 0, sizeof(seg));}
	void upd(int t, int i, int fr, int re) {
		if (!(fr<=t&&t<=re)) return ;
		seg[i]++;
		if (fr==re) return ;
		int md=(fr+re)/2;
		upd(t, i*2, fr, md);
		upd(t, i*2+1, md+1, re);
	}
	int sum(int s, int e, int i, int fr, int re) {
		if (fr>re) return 0;
		if (s<=fr&&re<=e) return seg[i];
		if (re<s||e<fr) return 0;
		int md=(fr+re)/2;
		return sum(s, e, i*2, fr, md)+sum(s, e, i*2+1, md+1, re);
	}
}S1, S2;*/

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	for (int i=0; i<A; i++) cp1.push_back(X[i]);
	for (int i=0; i<B; i++) cp2.push_back(Y[i]);
	for (int i=0; i<T; i++) {cp1.push_back(W[i]); cp2.push_back(S[i]);}
	sort(all(cp1)); cp1.erase(unique(all(cp1)), cp1.end());
	sort(all(cp2)); cp2.erase(unique(all(cp2)), cp2.end());
	for (int i=0; i<A; i++) X[i]=lower_bound(all(cp1), X[i])-cp1.begin();
	for (int i=0; i<B; i++) Y[i]=lower_bound(all(cp2), Y[i])-cp2.begin();
	for (int i=0; i<T; i++) {
		W[i]=lower_bound(all(cp1), W[i])-cp1.begin();
		S[i]=lower_bound(all(cp2), S[i])-cp2.begin();
	}
	sort(X, X+A); sort(Y, Y+B);
	for (int i=0; i<T; i++) ar.push_back({W[i], S[i]});
	sort(all(ar), [](pii x1, pii x2){return x1.fi==x2.fi?x1.se>x2.se:x1.fi>x2.fi;});

	for (int i=0; i<T; i++) if (X[A-1]<=W[i]&&Y[B-1]<=S[i]) return -1;
	int s=0, e=T;
	set<pii>::iterator ub;
	while (s+1<e) {
		ll md=(s+e+1)/2;
		int i;
		for (i=0; i<A; i++) S1.insert({X[i], i});
		for (i=0; i<B; i++) S2.insert({Y[i], i});
		fill(cn1, cn1+A, md);
		fill(cn2, cn2+B, md);
		for (i=0; i<T; i++) {
			ub=S2.upper_bound(make_pair(ar[i].se, A));
			if (ub!=S2.end()) {
				cn2[(*ub).se]--;
				if (cn2[(*ub).se]==0) S2.erase(ub);
			}
			else {
				ub=S1.upper_bound(make_pair(ar[i].fi, B));
				if (ub!=S1.end()) {
					cn1[(*ub).se]--;
					if (cn1[(*ub).se]==0) S1.erase(ub);
				}
				else break;
			}
		}
		if (i<T) s=md;
		else e=md;
	}
	return e;
}

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