| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 151822 | junodeveloper | Robots (IOI13_robots) | C++14 | 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>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int offset=1<<20;
int A,B,T;
int X[50010],Y[50010];
int a[1000010],b[1000010];
pii tree[2][4*1000010];
set<pii> st[2][1000010];
void Up(int t,int p) {
while(p>0) {
if(tree[t][p*2].fi>tree[t][p*2+1].fi)
tree[t][p]=tree[t][p*2];
else tree[t][p]=tree[t][p*2+1];
p/=2;
}
}
void Add(int t,int p,int x,int i) {
st[t][p].insert({x,i});
p+=offset;
tree[t][p]=*st[t][p-offset].rbegin();
Up(t,p/2);
}
void Remove(int t,int p,int x,int i) {
st[t][p].erase({x,i});
p+=offset;
if(!st[t][p-offset].empty())
tree[t][p]=*st[t][p-offset].rbegin();
else tree[t][p]={-1,-1};
Up(t,p/2);
}
pii query(int t,int l,int r) {
pii ret={-1,-1};
l+=offset,r+=offset;
while(1) {
if(ret.fi<tree[t][l].fi) ret=tree[t][l];
if(ret.fi<tree[t][r].fi) ret=tree[t][r];
if(l==r) break;
l=(l+1)>>1;
r=(r-1)>>1;
}
return ret;
}
int putaway (int A, int B, int T, int X[], int Y[], int W[], int S[]) {
int i,j;
for(i=0;i<4*1000010;i++)
tree[0][i]=tree[1][i]={-1,-1};
vector<int> v,w;
sort(X,X+A); sort(Y,Y+B);
for(i=0;i<T;i++) {
a[i]=W[i],b[i]=S[i];
v.push_back(a[i]);
w.push_back(b[i]);
}
sort(all(v));
v.erase(unique(all(v)),v.end());
sort(all(w));
w.erase(unique(all(w)),w.end());
for(i=0;i<A;i++) {
X[i]=lower_bound(all(v),X[i])-v.begin();
}
for(i=0;i<B;i++) {
Y[i]=lower_bound(all(w),Y[i])-v.begin();
}
for(i=0;i<T;i++){
a[i]=lower_bound(all(v),a[i])-v.begin()+1;
b[i]=lower_bound(all(w),b[i])-v.begin()+1;
Add(0,a[i],b[i],i);
Add(1,b[i],a[i],i);
}
int ans=0;
while(1) {
bool flag=false;
for(i=0;T&&i<A;i++) {
pii q=query(0,0,X[i]);
if(q.se==-1) continue;
Remove(0,a[q.se],b[q.se],q.se);
Remove(1,b[q.se],a[q.se],q.se);
T--; flag=true;
}
for(i=0;T&&i<B;i++) {
pii q=query(1,0,Y[i]);
if(q.se==-1) continue;
Remove(0,a[q.se],b[q.se],q.se);
Remove(1,b[q.se],a[q.se],q.se);
T--; flag=true;
}
ans++;
if(!T) break;
if(!flag) {
puts("-1");
return 0;
}
}
return ans;
}