| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1036945 | 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){ // replace with 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){ // [l, 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;
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){
if(a.first<b.first){
return a;
}
else{
return 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);
reverse(W,W+T);
sort(S,S+T);
reverse(S,S+T);
vector<pair<int,int>>x(A);
for(int i=0;i<A;i++){
x[i].first=0;
x[i].second=i;
}
vector<pair<int,int>>y(B);
for(int i=0;i<B;i++){
y[i].first=0;
y[i].second=i;
}
vector<int>xl(A,0);
vector<int>yl(B,0);
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);
for(int i=0;i<T;i++){
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;
}
else 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_x.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_x.update(mejor_s.second,(mejor_s.first+1));
}
}
}
return max(max_x.query(0,A-1),max_y.query(0,B-1));
}