Submission #405007

#	Time	Username	Problem	Language	Result	Execution time	Memory
405007		Aryan_Raina	Robots (IOI13_robots)	C++14	76 / 100	1158 ms	45592 KiB

robots

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

#define ar array
const int INF = 1e9+9;

template<class T> struct SegmentTree {
   	int n; vector<T> values; 
   	T IDENTITY;
   	SegmentTree(int n, T id) : n(n), values(2*n, IDENTITY = id) {}
   	T calc_op(T a, T b) { return max(a, b); }
   	void modify(int i, T v) {
      	for (values[i += n] = v; i >>= 1; ) 
         	values[i] = calc_op(values[2*i], values[2*i + 1]);
   	}
   	T calc(int l, int r) {
      	T rans = IDENTITY, lans = IDENTITY;
      	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
         	if (l & 1) lans = calc_op(lans, values[l++]);
         	if (r & 1) rans = calc_op(values[--r], rans);
      	}
      	return calc_op(lans, rans);
   	}
};

const int MX = 1000*1000 + 50*1000;
SegmentTree<ar<int,2>> xx(MX, {-INF, -1}), yy(MX, {-INF, -1});

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	int totx = 0, toty = 0;
	vector<ar<int,2>> shit;
	for (int i = 0; i < A; i++) shit.push_back({X[i], i});
	for (int i = 0; i < T; i++) shit.push_back({W[i], i + A});
	sort(shit.begin(), shit.end());
	for (auto i : shit) 
		if (i[1] < A) X[i[1]] = totx++;
		else W[i[1] - A] = totx++;

	shit.clear();
	for (int i = 0; i < B; i++) shit.push_back({Y[i], i});
	for (int i = 0; i < T; i++) shit.push_back({S[i], i + B});
	sort(shit.begin(), shit.end());
	for (auto i : shit) 
		if (i[1] < B) Y[i[1]] = toty++;
		else S[i[1] - B] = toty++;

	sort(X, X + A); sort(Y, Y + B);
	for (int i = 0; i < T; i++) {
		bool remdix = A - 1 < 0 || W[i] > X[A - 1];
		bool remdiy = B - 1 < 0 || S[i] > Y[B - 1];
		if (remdix && remdiy) return -1;
	}

	for (int i = 0; i < T; i++) 
		xx.modify(W[i], {S[i], i}), yy.modify(S[i], {W[i], i});

	int ans = 0;
	while (xx.calc(0, totx)[1] != -1 || yy.calc(0, toty)[1] != -1) {
		for (int i = 0; i < A; i++) {
			int rem = xx.calc(0, X[i])[1];
			if (rem == -1) continue;
			xx.modify(W[rem], {-INF, -1});
			yy.modify(S[rem], {-INF, -1});
		} 

		for (int i = 0; i < B; i++) {
			int rem = yy.calc(0, Y[i])[1];
			if (rem == -1) continue;
			xx.modify(W[rem], {-INF, -1});
			yy.modify(S[rem], {-INF, -1});
		} 

		++ans;
	}

    return ans;
}

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