Submission #151864

#	Time	Username	Problem	Language	Result	Execution time	Memory
151864		junodeveloper	Robots (IOI13_robots)	C++14	76 / 100	1701 ms	65540 KiB

robots

#include <bits/stdc++.h>
#include "robots.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 *val[2];
int tree[2][offset<<1];
set<pair<int,pii> > st[2];
void Up(int t,int h) {
	while(h>0) {
		if(tree[t][h*2+1]==-1||(tree[t][h*2]!=-1&&val[t][tree[t][h*2]]>val[t][tree[t][h*2+1]]))
			tree[t][h]=tree[t][h*2];
		else tree[t][h]=tree[t][h*2+1];
		h/=2;
	}
}
void Add(int t,int p,int x,int i) {
	st[t].insert({p,{x,i}});
	auto it=st[t].lower_bound({p+1,{-1,-1}}); it--;
	int h=p+offset;
	tree[t][h]=it->se.se;
	Up(t,h/2);
}
void Remove(int t,int p,int x,int i) {
	st[t].erase({p,{x,i}});
	auto it=st[t].lower_bound({p+1,{-1,-1}});
	int h=p+offset;
	if(it!=st[t].begin()) {
		it--;
		if(it->fi==p) {
			tree[t][h]=it->se.se;
		} else tree[t][h]=-1;
	} else tree[t][h]=-1;
	Up(t,h/2);
}
int query(int t,int l,int r) {
	int ret=-1;
	l+=offset,r+=offset;
	while(1) {
		if(ret==-1||(tree[t][l]!=-1&&val[t][ret]<val[t][tree[t][l]])) ret=tree[t][l];
		if(ret==-1||(tree[t][r]!=-1&&val[t][ret]<val[t][tree[t][r]])) 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;
	memset(tree,-1,sizeof(tree));
	vector<int> v,w;
	sort(X,X+A); sort(Y,Y+B);
	val[0]=S,val[1]=W;
	for(i=0;i<T;i++) {
		v.push_back(W[i]);
		w.push_back(S[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])-w.begin();
	}
	for(i=0;i<T;i++){
		W[i]=lower_bound(all(v),W[i])-v.begin()+1;
		S[i]=lower_bound(all(w),S[i])-w.begin()+1;
		Add(0,W[i],S[i],i);
		Add(1,S[i],W[i],i);
	}
	int ans=0;
	while(1) {
		bool flag=false;
		for(i=0;T&&i<A;i++) {
			int q=query(0,0,X[i]);
			if(q==-1) continue;
			Remove(0,W[q],S[q],q);
			Remove(1,S[q],W[q],q);
			T--; flag=true;
		}
		for(i=0;T&&i<B;i++) {
			int q=query(1,0,Y[i]);
			if(q==-1) continue;
			Remove(0,W[q],S[q],q);
			Remove(1,S[q],W[q],q);
			T--; flag=true;
		}
		ans++;
		if(!T) break;
		if(!flag) {
			return -1;
		}
	}
	return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:56:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^

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