Submission #134420

#	Time	Username	Problem	Language	Result	Execution time	Memory
134420		arthurconmy	Robots (IOI13_robots)	C++14	100 / 100	1994 ms	65536 KiB

robots

#include <bits/stdc++.h>
 
#ifndef ARTHUR_LOCAL
	#include "robots.h"
#endif
 
using namespace std;
using pii=pair<int,int>;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
 
const int p2 = 65536;
pii st[2][p2+p2];
 
pii query(int l, int r, int st_type)
{
	l+=p2; // I ... think this indexing is right
	r+=p2;
 
	pii ans = mp(int(1e9),int(1e9));
 
	while(l<=r)
	{
		if(l%2 == 1) ans=min(ans,st[st_type][l++]);
		if(r%2 == 0) ans=min(ans,st[st_type][r--]);
 
		l/=2;
		r/=2;
	}
 
	return ans;
}
 
void update(int k, int st_type)
{
	// cout << k << " " << st_type << endl;
 
	k+=p2+1;
	st[st_type][k] = mp(st[st_type][k].ff+1, st[st_type][k].ss);
	k/=2;
 
	// cout << st[st_type][k].ff+1 << " " << st[st_type][k].ss << "NEW" << endl;
 
	while(k>=1)
	{
		st[st_type][k] = min(st[st_type][k+k],st[st_type][k+k+1]);
		k/=2;
	}
}
 
int putaway(int a, int b, int t, int X_raw[], int Y_raw[], int W_raw[], int S_raw[])
{
	vector<int> X,Y,W,S;
	vector<pii> toys;
 
	for(int i=0; i<1000000; i++)
	{
		if(i<a) X.pb(X_raw[i]);
		if(i<b) Y.pb(Y_raw[i]);
		if(i<t) W.pb(W_raw[i]);
		if(i<t) S.pb(S_raw[i]);
	
		if(i<t) toys.pb(mp(S_raw[i],W_raw[i]));
	}
 
	sort(X.rbegin(),X.rend());
	sort(Y.rbegin(),Y.rend());
	
	sort(W.rbegin(),W.rend());
	sort(S.rbegin(),S.rend());
 
	map<int,int> W_comp;
	map<int,int> S_comp;
 
	// coordinate compress everything
 
	int cur_x=0;
 
	for(int i=0; i<t; i++) // compress W
	{
		while(cur_x < a && X[cur_x]>W[i]) cur_x++;
		W_comp[W[i]]=cur_x;
		//cout << "W " << W[i] << " " << cur_x << endl;
	}
 
	// cout << endl;
 
	int cur_y=0;
 
	for(int i=0; i<t; i++) // compress W
	{
		while(cur_y < b && Y[cur_y]>S[i]) cur_y++;
		S_comp[S[i]]=cur_y;
		//cout << "S " << S[i] << " " << cur_y << endl;
	}
 
	for(int i=0; i<t; i++)
	{
		pii P = toys[i];
		//cout << P.ff << " " << P.ss << ": ";
		toys[i] = {S_comp[P.ff],W_comp[P.ss]};
		//cout << toys[i].ff << " " << toys[i].ss << endl;
 
		if(toys[i] == mp(0,0)) return -1;
	}
 
	sort(toys.begin(), toys.end());
 
	// now things are ordered S then W ... because
 
	for(int i=0; i<2; i++)
	{
		for(int j=1; j<p2+p2; j++)
		{
			st[i][j]=mp(int(1e9),int(1e9));
		}
	}
 
	for(int i=0; i<b; i++)
	{
		st[0][i+p2+1] = mp(0,-i); // 0-indexed hmm ... ?
	}
 
	for(int i=0; i<a; i++)
	{
		st[1][i+p2+1] = mp(0,-i);
	}
 
	for(int i=p2-1; i>=1; i--)
	{
		st[0][i]=min(st[0][i+i],st[0][i+i+1]);
		st[1][i]=min(st[1][i+i],st[1][i+i+1]);
	}
 
	//cout << endl;
 
	for(int i=0; i<t; i++)
	{
		//cout << toys[i].ff << " " << toys[i].ss << endl;
	
		pii S_cur = query(1,toys[i].ff,0);
		pii W_cur = query(1,toys[i].ss,1);
 
		//cout << S_cur.ff << " " << S_cur.ss << endl;
		//cout << W_cur.ff << " " << W_cur.ss << endl << endl;
 
		// if(toys[i].ss==3) cout << st[1][p2].ff << " " << st[1][p2+1].ff << " " << st[1][p2+2].ff << " " << st[1][p2+3].ff << endl;
 
		if(S_cur.ff < W_cur.ff)
		{
			update(-S_cur.ss,0);
		}
 
		else 
		{
			update(-W_cur.ss,1);
		}
	}
 
	int ans=0;
 
	for(int i=0; i<max(a,b); i++)
	{
		if(i<b) ans=max(ans,st[0][i+1+p2].ff);
		if(i<a) ans=max(ans,st[1][i+1+p2].ff);
	}
 
	return ans;
}

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