Submission #56808

#	Time	Username	Problem	Language	Result	Execution time	Memory
56808		hamzqq9	Robots (IOI13_robots)	C++14	100 / 100	2371 ms	64628 KiB

robots

#include "robots.h"
 
#include<bits/stdc++.h>
using namespace std;
 
#define ii pair<int,int>
#define st first
#define nd second
#define orta ((bas+son)/2)
 
#define MAX1 1000005
#define MAX2 50005
 
int A,B,T;
int X[MAX2],Y[MAX2];
ii toy[MAX1];
bool S[MAX2*4];
int fr[2][MAX2];
int DAYS;

void build(int node,int bas,int son) {
 
	if(bas>son) return ;

	if(bas==son) {
 
		S[node]=true;
 
		return ;
 
	}
 
	build(node*2,bas,orta);
	build(node*2+1,orta+1,son);
 
	S[node]=S[node*2]|S[node*2+1];
 
}
 
priority_queue<int> H;

void zero() {

	while(!H.empty()) H.pop();
 
	build(1,0,B-1);

	for(int i=0;i<A;i++) fr[0][i]=0;
	for(int i=0;i<B;i++) fr[1][i]=0;
 
}
 
void up(int node,int bas,int son,int x) {

	if(bas>x || son<x) return ;
 
	if(bas==x && son==x) {
 
		S[node]=false;
 
		return ;
 
	}
 
	up(node*2,bas,orta,x);
	up(node*2+1,orta+1,son,x);
 
	S[node]=S[node*2]|S[node*2+1];
 
}

int get(int node,int bas,int son,int x,int y) {

	if(bas>=x && son<=y) {
 
		if(!S[node]) return bas;

		if(bas==son) return bas;	
		
		if(S[node*2]) return get(node*2,bas,orta,x,y);
		
		return get(node*2+1,orta+1,son,x,y);
 
	}
 
	if(orta>=x) {
 
		if(orta+1<=y) {
 
			int L=get(node*2,bas,orta,x,y);
 
			if(fr[1][L]<DAYS) return L;
 
			return get(node*2+1,orta+1,son,x,y);
 
		}
 
		return get(node*2,bas,orta,x,y);
 
	}
 
	return get(node*2+1,orta+1,son,x,y);
 
}
 
priority_queue<int> LST;

bool check() {
 
	zero();

	while(!LST.empty()) LST.pop();
 
	int last=A;

	for(int i=0;i<T;i++) {

		while(last-1>=0 && X[last-1]>=toy[i].st) {
			
			last--; 
 		
			LST.push(-last);

 		}

 		int cur=last;

 		while(!LST.empty()) {

 			int tp=-LST.top();

 			if(fr[0][tp]==DAYS) {
 			
 				LST.pop();

 				continue ;
			
			}

 			cur=tp;

 			break ;

 		}

		H.push(-toy[i].nd);

		if(last==A || fr[0][cur]==DAYS) {
 
			int valB=-H.top();
 
			H.pop();
 
			int pos=lower_bound(Y,Y+B,valB)-Y;
 
			int RASB=(pos<B?get(1,0,B-1,pos,B-1):-1);
 
			if(pos==B || fr[1][RASB]==DAYS) {

				return false;
 
			}
			else {
 
				fr[1][RASB]++;

				if(fr[1][RASB]==DAYS) {

					up(1,0,B-1,RASB);
	 
				}

			}
 
		}
		else {

			fr[0][cur]++;

		}
 
	}
 
	return true;
 
}
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
 
	::A=A;
	::B=B;
	::T=T;
 
	for(int i=0;i<A;i++) {
 
		X[i]--;
		::X[i]=X[i];
 
	}
 
	for(int i=0;i<B;i++) {
 
		Y[i]--;
		::Y[i]=Y[i];
 
	}

	for(int i=0;i<T;i++) {
 
		toy[i]={W[i],S[i]};
 
	}
 
	sort(::X,::X+A);
	sort(::Y,::Y+B);
 
	sort(toy,toy+T,greater<ii>());

	int bas=1,son=T;
 
	while(bas<=son) {
 
		DAYS=orta;

		if(check()) son=orta-1;
		else bas=orta+1;
 
	}
 
	if(bas==T+1) {
 
		return -1;
 
	}
 
	return bas;
 
}

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