Submission #813552

#	Time	Username	Problem	Language	Result	Execution time	Memory
813552		I_Love_EliskaM_	Robots (IOI13_robots)	C++17	90 / 100	479 ms	65536 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

struct sgt {
	vector<int> t,a; int sz=1,n;
	sgt(int _n) {
		n=_n;
		while (sz<n) sz<<=1;
		t.assign(2*sz,n);
		a.assign(n+1,-1);
		forn(i,n) t[sz-1+i]=i;
	}
	int merge(int i, int j) {
		if (a[i]>a[j]) return i;
		else return j;
	}
	void upd(int v, int l, int r, int i) {
		if (r-l==1) return;
		int m=(l+r)>>1;
		if (i<m) upd(2*v+1,l,m,i);
		else upd(2*v+2,m,r,i);
		t[v]=merge(t[2*v+1],t[2*v+2]);
	}
	void set(int i, int x) {
		a[i]=x;
		upd(0,0,sz,i);
	}
	int query(int v, int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return n;
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		int lq=query(2*v+1,l,m,lx,rx);
		int rq=query(2*v+2,m,r,lx,rx);
		return merge(lq,rq);
	}
	int query(int l, int r) {
		return query(0,0,sz,l,r);
	}
};

int p2(int n, int b, int m, int x[], int y[], int w[], int s[]) {
	int tot=m;
	set<pi> st;
	forn(i,m) st.insert({w[i],i});
	int ans=0;
	while (tot) {
		forn(i,n) {
			auto it=st.lower_bound({x[i],-1});
			if (it==st.begin()) continue;
			--it;
			--tot;
			st.erase(it);
			if (!tot) break;
		}
		++ans;
	}
	return ans;
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
	if (a) sort(x,x+a);
	if (b) sort(y,y+b);
	forn(i,t) {
		int z=0;
		if (a) z|=w[i]<x[a-1];
		if (b) z|=s[i]<y[b-1];
		if (!z) return -1;
	}
	if (b==0) return p2(a,b,t,x,y,w,s);
	if (a==0) return p2(b,a,t,y,x,s,w);

	vector<int> pos1(t), pos2(t);
	vector<int> un1(t), un2(t);
	vector<int> vis(t);
	set<pi> s1, s2;
	forn(i,t) {
		s1.insert({w[i],i});
		s2.insert({s[i],i});
	}
	int m;
	m=0;
	for(auto&x:s1) pos1[x.s]=m++;
	m=0;
	for(auto&x:s2) pos2[x.s]=m++;
	forn(i,t) un1[pos1[i]]=i;
	forn(i,t) un2[pos2[i]]=i;

	sgt st1(t), st2(t);
	forn(i,t) {
		st1.set(pos1[i],s[i]);
		st2.set(pos2[i],w[i]);
	}

	int tot=t;
	int ans=0;
	while (tot) {

		int l=0, r=min(tot,a);
		while (l<r) {
			int mid=(l+r+1)>>1;
			auto it=s1.begin();
			int z=1;
			for (int i=a-mid; i<a; ++i) {
				z&=x[i]>(*it).f;
				++it;
			}
			if (z) l=mid;
			else r=mid-1;
		}
		for (int i=a-r; i<a; ++i) {
			auto it=s1.lower_bound({x[i],-1});
			if (it==s1.begin()) continue;
			it--;
			int j=(*it).s;
			j=pos1[j];
			int j2 = st1.query(0,j+1);
			int j3 = un1[j2];
			if (vis[j3]) exit(0);
			assert(!vis[j3]);
			vis[j3]=1;
			st1.set(pos1[j3],-2);
			st2.set(pos2[j3],-2);
			s1.erase({w[j3],j3});
			s2.erase({s[j3],j3});
		}
		tot-=r;

		l=0, r=min(tot,b);
		while (l<r) {
			int mid=(l+r+1)>>1;
			auto it=s2.begin();
			int z=1;
			for (int i=b-mid; i<b; ++i) {
				z&=y[i]>(*it).f;
				++it;
			}
			if (z) l=mid;
			else r=mid-1;
		}
		for (int i=b-r; i<b; ++i) {
			auto it=s2.lower_bound({y[i],-1});
			if (it==s2.begin()) continue;
			it--;
			int j=(*it).s;
			j=pos2[j];
			int j2 = st2.query(0,j+1);
			int j3 = un2[j2];
			assert(!vis[j3]);
			vis[j3]=1;
			st1.set(pos1[j3],-2);
			st2.set(pos2[j3],-2);
			s1.erase({w[j3],j3});
			s2.erase({s[j3],j3});
		}
		tot-=r;

		++ans;
	}

	return ans;
}

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