Submission #373753

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

robots

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

using namespace std;

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

struct Node
{
	pair<int, int> mn;
	pair<int, int> mx;

	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) {
		if (l == r) {
			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) {
			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];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	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++) {
		pair<int, int> valor(0, Y[i]);
		seg_small.update(1, 1, m, valor);
	}
	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);
		if (weak.mn.first == INF && small.mn.first == INF) {
			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 {
			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