Submission #762282

#	Time	Username	Problem	Language	Result	Execution time	Memory
762282		SanguineChameleon	Robots (IOI13_robots)	C++17	100 / 100	1566 ms	29600 KiB

robots

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

const int maxN = 1e6 + 20;
const int maxB = 5e4 + 20;
pair<int, int> W[maxN];
pair<int, int> S[maxN];
pair<int, int> cnt[maxN];
long long tree[maxB * 4];
int lazy[maxB * 4];
int A, B, N, K;

void build(int id, int lt, int rt) {
	lazy[id] = 0;
	if (lt == rt) {
		tree[id] = -1LL * lt * K;
		return;
	}
	int mt = (lt + rt) >> 1;
	build(id << 1, lt, mt);
	build(id << 1 | 1, mt + 1, rt);
	tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}

void update(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		tree[id]++;
		lazy[id]++;
		return;
	}
	tree[id << 1] += lazy[id];
	lazy[id << 1] += lazy[id];
	tree[id << 1 | 1] += lazy[id];
	lazy[id << 1 | 1] += lazy[id];
	lazy[id] = 0;
	int mt = (lt + rt) >> 1;
	if (qr <= mt) {
		update(id << 1, lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		update(id << 1 | 1, mt + 1, rt, ql, qr);
	}
	else {
		update(id << 1, lt, mt, ql, mt);
		update(id << 1 | 1, mt + 1, rt, mt + 1, qr);
	}
	tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}

bool check(int _K) {
	K = _K;
	build(1, 0, B);
	for (int i = 0; i < N; i++) {
		update(1, 0, B, cnt[i].second, B);
		if (tree[1] > 1LL * cnt[i].first * K) {
			return false;
		}
	}
	return true;
}

int putaway(int _A, int _B, int _N, int X[], int Y[], int _W[], int _S[]) {
	A = _A;
	B = _B;
	N = _N;
	for (int i = 0; i < N; i++) {
		W[i].first = _W[i];
		W[i].second = i;
	}
	for (int i = 0; i < N; i++) {
		S[i].first = _S[i];
		S[i].second = i;
	}
	sort(W, W + N, greater<pair<int, int>>());
	sort(S, S + N, greater<pair<int, int>>());
	sort(X, X + A, greater<int>());
	sort(Y, Y + B, greater<int>());
	int lt = -1;
	for (int i = 0; i < N; i++) {
		while (lt < A - 1 && X[lt + 1] > W[i].first) {
			lt++;
		}
		cnt[W[i].second].first = lt + 1;
	}
	lt = -1;
	for (int i = 0; i < N; i++) {
		while (lt < B - 1 && Y[lt + 1] > S[i].first) {
			lt++;
		}
		cnt[S[i].second].second = lt + 1;
	}
	if (A < B) {
		for (int i = 0; i < N; i++) {
			swap(cnt[i].first, cnt[i].second);
		}
		swap(A, B);
	}
	sort(cnt, cnt + N);
	lt = 1;
	int rt = N;
	int res = -1;
	while (lt <= rt) {
		int mt = (lt + rt) >> 1;
		if (check(mt)) {
			res = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

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