Submission #373752

#	Time	Username	Problem	Language	Result	Execution time	Memory
373752		morato	Robots (IOI13_robots)	C++17	0 / 100	53 ms	65540 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

const int N = 1050000;
const int M = 500005;
const int INF = 1e9;

struct Node
{
	pair<int, int> mn; // valor, indice
	pair<int, int> mx; // valor, indice

	Node() {
		mn = {INF, 0};
		mx = {-1, 0};
	}

	Node(pair<int, int> a, pair<int, int> b): mn(a), mx(b) {}

	Node operator+(Node other) {
		return Node(min(mn, other.mn), max(mx, other.mx));
	}
};

struct SegTree
{
	Node seg[4 * N];

	void update(int node, int l, int r, pair<int, int> x) {
		// cout << node << ' ' << l << ' ' << r << " {" << x.first << ", " << x.second << "}\n";
		if (l == r) {
			//assert(l == x.second);
			// cout << seg[node].mn.first << " -> " << x.first << '\n';
			seg[node] = Node(x, x);
		} else {
			int m = (l + r) >> 1;
			if (x.second <= m) {
				update(2 * node, l, m, x);
			} else {
				update(2 * node + 1, m + 1, r, x);
			}
			seg[node] = seg[2 * node] + seg[2 * node + 1];
		}
	}

	Node query(int node, int l, int r, int ql, int qr) {
		if (ql > r || l > qr) {
			return Node({INF, 0}, {-1, 0});
		}
		if (ql <= l && r <= qr) {
			// cout << seg[node].mn.first << " " << seg[node].mn.second << '\n';
			return seg[node];
		}
		int m = (l + r) >> 1;
		return query(2 * node, l, m, ql, qr) + query(2 * node + 1, m + 1, r, ql, qr);
	}

} seg_weak, seg_small;

vector<pair<int, pair<int, int>>> compress[2]; // comprimir pesos e alturas

/*
int A, B, T, X[M], Y[M], W[N], S[N];

void read() {
	cin >> A >> B >> T;
	for (int i = 0; i < A; i++) cin >> X[i];
	for (int i = 0; i < B; i++) cin >> Y[i];
	for (int i = 0; i < T; i++) {
		cin >> W[i] >> S[i];
	}
}*/

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
/*int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	read();*/
	for (int i = 0; i < A; i++) {
		compress[0].push_back({X[i], {0, i}});
	}
	for (int i = 0; i < B; i++) {
		compress[1].push_back({Y[i], {0, i}});
	}
	for (int i = 0; i < T; i++) {
		compress[0].push_back({W[i], {1, i}});
		compress[1].push_back({S[i], {1, i}});
	}
	sort(compress[0].begin(), compress[0].end());
	sort(compress[1].begin(), compress[1].end());
	for (int i = 0; i < (int) compress[0].size(); i++) {
		if (compress[0][i].second.first) {
			W[compress[0][i].second.second] = i + 1;
		} else {
			X[compress[0][i].second.second] = i + 1;
		}
	}
	for (int i = 0; i < (int) compress[1].size(); i++) {
		if (compress[1][i].second.first) {
			S[compress[1][i].second.second] = i + 1;
		} else {
			Y[compress[1][i].second.second] = i + 1;
		}
	}
	int n = (int) compress[0].size();
	int m = (int) compress[1].size();
	for (int i = 0; i < A; i++) {
		pair<int, int> valor(0, X[i]);
		seg_weak.update(1, 1, n, valor);
		
	}
	for (int i = 0; i < B; i++) {
		// cout << Y[i] << ' ';
		pair<int, int> valor(0, Y[i]);
		seg_small.update(1, 1, m, valor);
	}
	// cout << '\n';
	for (int i = 0; i < T; i++) {
		Node weak = seg_weak.query(1, 1, n, W[i] + 1, n);
		Node small = seg_small.query(1, 1, m, S[i] + 1, m);
		// cout << "WEAK [" << W[i] << ", " << n << "] = " << weak.mn.first << "(" << weak.mn.second << ")\n";
		// cout << "SMALL [" << S[i] << ", " << m << "] = " << small.mn.first << "(" << small.mn.second << ")\n";
		// cout << '\n';
		if (weak.mn.first == INF && small.mn.first == INF) {
			// cout << "DEU BOSTA\n";
			// break;
			return -1;
		} else if (weak.mn.first < small.mn.first) {
			pair<int, int> novo(weak.mn.first + 1, weak.mn.second);
			seg_weak.update(1, 1, n, novo);
		} else {
			// cout << small.mn.first << " -> " << small.mn.first + 1 << '\n';
			pair<int, int> novo(small.mn.first + 1, small.mn.second);
			seg_small.update(1, 1, m, novo);
		}
	}
	return max(seg_weak.seg[1].mx.first, seg_small.seg[1].mx.first);
}

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