Submission #257894

#	Time	Username	Problem	Language	Result	Execution time	Memory
257894		ChrisT	Robots (IOI13_robots)	C++17	76 / 100	1773 ms	65536 KiB

robots

#include <algorithm>
#include <vector>
#include <map>
#include "robots.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e6 + 5, LOG = 18, MOD = 1e9 + 7;
struct Point {
	int x,y;
	bool operator< (const Point &o) const {
		return make_pair(x,y) < make_pair(o.x,o.y);
	}
};
bool cmp (const Point &a, const Point &b) {return make_pair(a.y,a.x) < make_pair(b.y,b.x);}
struct Segtree {
	pii tree[2097155];
	void build (int ind, int l, int r, vector<int> &v) {
		if (l == r) return (void) (tree[ind] = {v[l-1],l-1});
		int mid = (l + r) / 2;
		build(lc,l,mid,v); build(rc,mid+1,r,v);
		tree[ind] = max(tree[lc],tree[rc]);
	} 
	int findfirst (int ind, int l, int r) {
		if (l == r) return tree[ind].first > 0 ? l-1 : -1;
		int mid = (l + r) / 2;
		if (tree[lc].first > 0) return findfirst(lc,l,mid);
		return findfirst(rc,mid+1,r);   
	} 
	void update (int ind, int l, int r, int i, int v) {
		if (l == r) return (void) (tree[ind] = {v,l-1});
		int mid = (l + r) / 2;
		if (i <= mid) update(lc,l,mid,i,v);
		else update(rc,mid+1,r,i,v);
		tree[ind] = max(tree[lc],tree[rc]);
	}
	pii query (int ind, int tl, int tr, int l, int r) {
		if (tl > r || tr < l) return {-1,-1};
		if (l <= tl && tr <= r) return tree[ind];
		int mid = (tl + tr) / 2;
		return max(query(lc,tl,mid,l,r),query(rc,mid+1,tr,l,r));
	}
} xSeg, ySeg;
int putaway (int a, int b, int t, int *x, int *y, int *w, int *s) { //2 segtree + bsearch
	sort(x,x+a); sort(y,y+b); 
	vector<Point> xSrt(t), ySrt(t);
	for (int i = 0; i < t; i++) xSrt[i] = ySrt[i] = {w[i],s[i]};
	sort(xSrt.begin(),xSrt.end());
	sort(ySrt.begin(),ySrt.end(),cmp);
	vector<int> temp(t);
	for (int i = 0; i < t; i++) temp[i] = xSrt[i].y;
	xSeg.build(1,1,t,temp);
	for (int i = 0; i < t; i++) temp[i] = ySrt[i].x;
	ySeg.build(1,1,t,temp);
	map<Point,int> taken;
	auto del = [&] (Point &p) {
		//printf ("p {%d,%d}\n",p.x,p.y);
		int posX = lower_bound(xSrt.begin(),xSrt.end(),p) - xSrt.begin() + taken[p];
		int posY = lower_bound(ySrt.begin(),ySrt.end(),p,cmp) - ySrt.begin() + taken[p];
		taken[p]++; 
		//printf ("posX %d posY %d\n",posX,posY);
		xSeg.update(1,1,t,posX+1,-1e9); ySeg.update(1,1,t,posY+1,-1e9);
	};
	int ret = 0, done = 0;
	while (done < t) {
		++ret; bool add = 0; 
		int lstLine = -1;
		while (1) {
			int go = xSeg.findfirst(1,1,t);
			//printf ("go %d\n",go);
			if (go == -1) break;
			int nxtLine = max(lstLine + 1,(int)(upper_bound(x,x+a,xSrt[go].x)-x));
			//printf ("nxtLine %d\n",nxtLine);
			if (nxtLine >= a) break;
			int ed = lower_bound(xSrt.begin(),xSrt.end(),Point{x[nxtLine],0})-xSrt.begin();
			//printf ("ed %d\n",ed);
			int take = xSeg.query(1,1,t,1,ed).second;
			//printf ("take %d\n",take);
			del(xSrt[take]); add = 1; ++done; lstLine = nxtLine;
		}
		lstLine = -1;
		while (1) {
			int go = ySeg.findfirst(1,1,t);
			//printf ("y go %d\n",go);
			if (go == -1) break;
			int nxtLine = max(lstLine + 1,(int)(upper_bound(y,y+b,ySrt[go].y)-y));
			//printf ("y nxtLine %d\n",nxtLine);
			if (nxtLine >= b) break;
			int ed = lower_bound(ySrt.begin(),ySrt.end(),Point{0,y[nxtLine]},cmp)-ySrt.begin();
			//printf ("y ed %d\n",ed);
			int take = ySeg.query(1,1,t,1,ed).second;
			//printf ("y take %d\n",take);
			del(ySrt[take]); add = 1; ++done; lstLine = nxtLine;
		}
		if (!add) return -1;
	}
	return ret;
}

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