| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1036949 | aaaaaarroz | Robots (IOI13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
template<class T, T m_(T, T)> struct IterativeSegmentTree {
int n;
vector<T> ST;
IterativeSegmentTree() {}
IterativeSegmentTree(vector<T> &a) {
n = a.size();
ST.resize(n << 1);
for (int i = n; i < (n << 1); i++)
ST[i] = a[i - n];
for (int i = n - 1; i > 0; i--)
ST[i] = m_(ST[i << 1], ST[i << 1 | 1]);
}
void update(int pos, T val) {
ST[pos += n] = val;
for (pos >>= 1; pos > 0; pos >>= 1)
ST[pos] = m_(ST[pos << 1], ST[pos << 1 | 1]);
}
T query(int l, int r) {
T ansL, ansR;
bool hasL = 0, hasR = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ansL = (hasL ? m_(ansL, ST[l]) : ST[l]), hasL = 1, l++;
if (r & 1)
ansR = (hasR ? m_(ST[--r], ansR) : ST[--r]), hasR = 1;
}
if (!hasL) return ansR;
if (!hasR) return ansL;
return m_(ansL, ansR);
}
};
pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
return (a.first < b.first) ? a : b;
}
int merge2(int a, int b) {
return max(a, b);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
sort(X, X + A);
sort(Y, Y + B);
sort(W, W + T);
sort(S, S + T);
vector<pair<int, int>> x(A);
vector<pair<int, int>> y(B);
vector<int> xl(A, 0);
vector<int> yl(B, 0);
for (int i = 0; i < A; i++) x[i] = {0, i};
for (int i = 0; i < B; i++) y[i] = {0, i};
IterativeSegmentTree<pair<int, int>, merge> XX(x);
IterativeSegmentTree<pair<int, int>, merge> YY(y);
IterativeSegmentTree<int, merge2> max_x(xl);
IterativeSegmentTree<int, merge2> max_y(yl);
vector<int> toy_idx(T);
iota(toy_idx.begin(), toy_idx.end(), 0);
sort(toy_idx.begin(), toy_idx.end(), [&](int i, int j) {
return W[i] < W[j] || (W[i] == W[j] && S[i] < S[j]);
});
for (int i : toy_idx) {
int weight = W[i];
int size = S[i];
auto itr1 = upper_bound(X, X + A, weight);
auto itr2 = upper_bound(Y, Y + B, size);
if (itr1 == X + A && itr2 == Y + B) {
return -1;
}
if (itr2 == Y + B) {
int pos_w = itr1 - X;
pair<int, int> mejor_w = XX.query(pos_w, A - 1);
XX.update(mejor_w.second, {mejor_w.first + 1, mejor_w.second});
max_x.update(mejor_w.second, (mejor_w.first + 1));
} else if (itr1 == X + A) {
int pos_s = itr2 - Y;
pair<int, int> mejor_s = YY.query(pos_s, B - 1);
YY.update(mejor_s.second, {mejor_s.first + 1, mejor_s.second});
max_y.update(mejor_s.second, (mejor_s.first + 1));
} else {
int pos_w = itr1 - X;
int pos_s = itr2 - Y;
pair<int, int> mejor_w = XX.query(pos_w, A - 1);
pair<int, int> mejor_s = YY.query(pos_s, B - 1);
if (mejor_w.first <= mejor_s.second) {
XX.update(mejor_w.second, {mejor_w.first + 1, mejor_w.second});
max_x.update(mejor_w.second, (mejor_w.first + 1));
} else {
YY.update(mejor_s.second, {mejor_s.first + 1, mejor_s.second});
max_y.update(mejor_s.second, (mejor_s.first + 1));
}
}
}
return max(max_x.query(0, A - 1), max_y.query(0, B - 1));
}