Submission #1013102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013102		AmirAli_H1	Robots (IOI13_robots)	C++17	100 / 100	2349 ms	21264 KiB

robots

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;
const int maxs = 5e4 + 4;

int n, m1, m2, R;
pii A[maxn]; int A1[maxs], A2[maxs];
int t[4 * maxs];

bool cmp(pii a, pii b) {
	if (a.S != b.S) return (a.S < b.S);
	else return (a.F > b.F);
}

void build(int v, int tl, int tr) {
	if (tr - tl <= 0) return ;
	if (tr - tl == 1) {
		t[v] = R;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = (t[2 * v + 1] + t[2 * v + 2] >= 1);
}

void add_val(int v, int tl, int tr, int i, int x) {
	if (tr - tl <= 0) return ;
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] += x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, i, x); add_val(2 * v + 2, mid, tr, i, x);
	t[v] = (t[2 * v + 1] + t[2 * v + 2] >= 1);
}

int get_ind(int v, int tl, int tr, int x) {
	if (tr - tl <= 0) return -1;
	if (tl >= x || t[v] == 0) return -1;
	if (tr - tl == 1) return tl;
	int mid = (tl + tr) / 2;
	int j = get_ind(2 * v + 2, mid, tr, x);
	if (j != -1) return j;
	else return get_ind(2 * v + 1, tl, mid, x);
}

bool ok(int valx) {
	R = valx;
	build(0, 0, m1); pii val = Mp(0, R);
	for (int i = 0; i < n; i++) {
		int x = A[i].F, y = A[i].S;
		int j = get_ind(0, 0, m1, x);
		if (j != -1) {
			add_val(0, 0, m1, j, -1);
		}
		else {
			if (val.F < y) {
				val.S--;
				if (val.S == 0) val = Mp(val.F + 1, R);
			}
			else return 0;
		}
	}
	return 1;
}

int putaway(int Ax, int Bx, int Tx, int X[], int Y[], int W[], int S[]) {
	n = Tx; m1 = Ax; m2 = Bx;
	for (int i = 0; i < m1; i++) A1[i] = X[i];
	for (int i = 0; i < m2; i++) A2[i] = Y[i];
	sort(A1, A1 + m1); sort(A2, A2 + m2);
	
	for (int i = 0; i < n; i++) {
		int j1 = m1 - (upper_bound(A1, A1 + m1, W[i]) - A1);
		int j2 = m2 - (upper_bound(A2, A2 + m2, S[i]) - A2);
		A[i] = Mp(j1, j2);
		if (j1 == 0 && j2 == 0) return -1;
	}
	sort(A, A + n, cmp);
	
	int l = 0, r = n + 1;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (ok(mid)) r = mid;
		else l = mid;
	}
	return r;
}

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