Submission #171080

#	Time	Username	Problem	Language	Result	Execution time	Memory
171080		dennisstar	Robots (IOI13_robots)	C++11	14 / 100	543 ms	28820 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;

struct segTree {
	int seg[110000];
	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;
	int ub;
	int sz1=cp1.size(), sz2=cp2.size();
	while (s+1<e) {
		ll md=(s+e+1)/2;
		S1.init(); S2.init();
		int i;
		for (i=0; i<T; i++) {
			ub=upper_bound(Y, Y+B, ar[i].se)-Y;
			if (ub<B&&(ll)S2.sum(ub, B, 1, 0, B)<md*(B-ub)) S2.upd(ub, 1, 0, B);
			else {
				ub=upper_bound(X, X+A, ar[i].fi)-X;
				if (ub<A&&(ll)S1.sum(ub, A, 1, 0, A)<md*(A-ub)) S1.upd(ub, 1, 0, A);
				else break;
			}
		}
		if (i<T) s=md;
		else e=md;
	}
	return e;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:57:6: warning: unused variable 'sz1' [-Wunused-variable]
  int sz1=cp1.size(), sz2=cp2.size();
      ^~~
robots.cpp:57:22: warning: unused variable 'sz2' [-Wunused-variable]
  int sz1=cp1.size(), sz2=cp2.size();
                      ^~~

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