Submission #392633

#	Time	Username	Problem	Language	Result	Execution time	Memory
392633		Antekb	Robots (IOI13_robots)	C++14	90 / 100	3079 ms	21672 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=(1<<16);
long long M[2*N], lazy[2*N];
void init(){
	for(int i=0; i<2*N; i++){
		M[i]=0;
		lazy[i]=0;
	}
}
void prop(int v){
	if(v>=N)return;
	int l=2*v, r=2*v+1;
	lazy[l]+=lazy[v];
	lazy[r]+=lazy[v];
	M[l]+=lazy[v];
	M[r]+=lazy[v];
	lazy[v]=0;
}
void add(int v, int L, int R, int l, int r, int c){
	if(l==L && r==R){
		lazy[v]+=c;
		M[v]+=c;
		return;
	}
	int m=(L+R)>>1;
	prop(v);
	if(l<=m)add(2*v, L, m, l, min(r, m), c);
	if(r>m)add(2*v+1, m+1, R, max(m+1, l), r, c);
	M[v]=min(M[2*v], M[2*v+1]);
	return;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    pair<int, int> tab[T];
    for(int i=0; i<T; i++){
    	tab[i]={upper_bound(X, X+A, W[i])-X, upper_bound(Y, Y+B, S[i])-Y};
    	//if(tab[i].st==A && tab[i].nd==B)return -1;
    	//cout<<tab[i].st<<" "<<tab[i].nd<<"\n";
    }
    sort(tab, tab+T);
    int l=1, r=T+1;
    while(l<r){
    	int m=(l+r)/2;
    	init();
    	bool b=1;
    	int j=A-1;
    	for(int i=0; i<B; i++){
    		add(1, 0, N-1, 0, i, m);
    	}
    	//cout<<m<<"\n";
    	long long a=0;
    	int i=T-1;
    	while(i>=0){
    		while(j>=0 && j>=tab[i].st)j--, a+=m;
    		int c=1;
    		while(c<=i && tab[i-c]==tab[i])c++;
    		add(1, 0, N-1, 0, tab[i].nd, -c);
    		/*for(int i=0; i<2*N; i++)cout<<M[i]<<" ";
    		cout<<"\n";
    		for(int i=0; i<2*N; i++)cout<<lazy[i]<<" ";
    		cout<<"\n";*/
    		if(M[1]+a<0){
    			b=0;
    			//cout<<i<<"\n";
    			break;
    		}
    		i-=c;
    	}
    	//cout<<m<<" "<<b<<"\n";
    	if(b)r=m;
    	else l=m+1;
    }
    if(l==T+1)return -1;
    return l;
}

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