Submission #411560

#	Time	Username	Problem	Language	Result	Execution time	Memory
411560		Mlxa	Robots (IOI13_robots)	C++14	76 / 100	375 ms	18808 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "robots.h"

const int N = 1 << 16;
const int INF = 1e9;
const pii NO = {-INF, -1};

void build(pii t[]) {
	for (int i = N - 1; i > 0; --i) {
		t[i] = max(t[i + i], t[i + i + 1]);
	}
}
pii query(pii t[], int l, int r) {
	pii res = NO;
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			res = max(res, t[l++]);
		}
		if (r % 2 == 0) {
			res = max(res, t[r--]);
		}
	}
	return res;
}
void update(pii t[], int i, pii p) {
	t[i += N] = p;
	for (i /= 2; i > 0; i /= 2) {
		t[i] = max(t[i + i], t[i + i + 1]);
	}
}

vector<pii> byx[N], byy[N];
pair<int, int> tx[2 * N], ty[2 * N];

bool used[N];

void iter(int a, int b, int t, int w[], int s[]) {
	(void)t;
	for (int i = 0; i < a; ++i) {
		int j = query(tx, 0, i).y;
		while (j >= 0 && used[j]) {
			assert(byx[w[j]].size() && byx[w[j]].back().y == j);
			byx[w[j]].pop_back();
			update(tx, w[j], byx[w[j]].size() ? byx[w[j]].back() : NO);
			j = query(tx, 0, i).y;
		}
		if (j < 0) {
			continue;
		}
		used[j] = true;
	}
	for (int i = 0; i < b; ++i) {
		int j = query(ty, 0, i).y;
		while (j >= 0 && used[j]) {
			assert(byy[s[j]].size());
			assert(byy[s[j]].back().y == j);
			byy[s[j]].pop_back();
			update(ty, s[j], byy[s[j]].size() ? byy[s[j]].back() : NO);
			j = query(ty, 0, i).y;
		}
		if (j < 0) {
			continue;
		}
		used[j] = true;
	}
}

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) {
		w[i] = (int)(upper_bound(x, x + a, w[i]) - x);
		s[i] = (int)(upper_bound(y, y + b, s[i]) - y);
		// cout << w[i] << " " << s[i] << endl;
		byx[w[i]].emplace_back(s[i], i);
		byy[s[i]].emplace_back(w[i], i);
	}
	for (int i = 0; i < N; ++i) {
		sort(all(byx[i]));
		sort(all(byy[i]));
		tx[i + N] = byx[i].size() ? byx[i].back() : NO;
		ty[i + N] = byy[i].size() ? byy[i].back() : NO;
	}
	build(tx), build(ty);

	int ti = 0;
	while (1) {
		int was = (int)count(used, used + t, true);
		if (was == t) {
			break;
		}
		++ti;
		iter(a, b, t, w, s);
		int now = (int)count(used, used + t, true);
		if (was == now) {
			return -1;
		}
	}
	return ti;
}

#ifdef LC
#include "grader.c"
#endif

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