제출 #55276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55276		kingpig9	로봇 (IOI13_robots)	C++11	0 / 100	771 ms	66560 KiB

robots

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1 << 20;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void compress (vector<int> &v) {
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
}

int A, B, N;
int X[MAXN], Y[MAXN], W[MAXN], S[MAXN];
vector<int> twei, tsiz;

struct segtree {
	pii tree[2 * MAXN];
	multiset<int> st[MAXN];	//f(v1) = v2

	void init() {
		for (int i = 0; i < MAXN; i++) {
			tree[i + MAXN] = pii((st[i].empty() ? -1 : *st[i].rbegin()), i);
		}

		for (int i = MAXN - 1; i; i--) {
			tree[i] = max(tree[2 * i], tree[2 * i + 1]);
		}
	}

	void update (int x, int v) {
		tree[x += MAXN].fi = v;
		while (x >>= 1) {
			tree[x] = max(tree[x << 1], tree[(x << 1) | 1]);
		}
	}

	void remove (int x, int y) {
		auto it = st[x].find(y);
		assert(it != st[x].end());
		st[x].erase(it);
		update(x, (st[x].empty() ? -1 : *st[x].rbegin()));
	}

	pii query (int a, int b, int cur = 1, int lt = 0, int rt = MAXN) {
		if (rt <= a || b <= lt) {
			return pii(-1, -1);
		}

		if (a <= lt && rt <= b) {
			return tree[cur];
		}

		int mid = (lt + rt) / 2;
		return max(query(a, b, (cur << 1), lt, mid), query(a, b, ((cur << 1) | 1), mid, rt));
	}
};

segtree segws, segsw;	//f(w) = s, f(s) = w

int putaway (int aaa, int bbb, int nnn, int xxx[], int yyy[], int www[], int sss[]) {
	A = aaa;
	B = bbb;
	N = nnn;
	for (int i = 0; i < A; i++) {
		X[i] = xxx[i];
	}
	for (int i = 0; i < B; i++) {
		Y[i] = yyy[i];
	}
	for (int i = 0; i < N; i++) {
		W[i] = www[i];
		S[i] = sss[i];
		twei.push_back(W[i]);
		tsiz.push_back(S[i]);
	}

	compress(twei);
	compress(tsiz);

	for (int i = 0; i < A; i++) {
		X[i] = lower_bound(all(twei), X[i]) - twei.begin();
	}
	for (int i = 0; i < B; i++) {
		Y[i] = lower_bound(all(tsiz), Y[i]) - tsiz.begin();
	}
	sort(X, X + A);
	sort(Y, Y + B);

	for (int i = 0; i < N; i++) {
		W[i] = lower_bound(all(twei), W[i]) - twei.begin();
		S[i] = lower_bound(all(tsiz), S[i]) - tsiz.begin();
		if (W[i] >= X[A - 1] && S[i] >= Y[B - 1]) {
			return -1;
		}

		segws.st[W[i]].insert(S[i]);
		segsw.st[S[i]].insert(W[i]);
		//debug("(%d, %d)\n", W[i], S[i]);
	}

//	debug("TWEI:"); for (int i : twei) debug(" %d", i); debug("\n");
//	debug("TSIZ:"); for (int i : tsiz) debug(" %d", i); debug("\n");

	segws.init();
	segsw.init();

	int rescued = 0;
	int ans = 0;
	while (rescued < N) {
		for (int i = 0; i < A; i++) {
			//debug("X[i] = %d\n", X[i]);
			pii p = segws.query(0, X[i]);
			if (p.fi >= 0) {
				//debug("A remove weight = %d, size = %d\n", twei[p.se], tsiz[p.fi]);
				segws.remove(p.se, p.fi);
				segsw.remove(p.fi, p.se);
				rescued++;
			}
		}
		for (int i = 0; i < B; i++) {
			pii p = segsw.query(0, Y[i]);
			if (p.fi >= 0) {
				//debug("B remove weight = %d, size = %d\n", twei[p.fi], tsiz[p.se]);
				segsw.remove(p.se, p.fi);
				segws.remove(p.fi, p.se);
				rescued++;
			}
		}
		ans++;
	}
	return ans;
}

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