Submission #384013

#	Time	Username	Problem	Language	Result	Execution time	Memory
384013		alireza_kaviani	Robots (IOI13_robots)	C++11	100 / 100	2491 ms	16160 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define all(x)			(x).begin() , (x).end()
#define lc				id << 1
#define rc				lc | 1

const int MAXN = 1e5 + 100;

int n , lz[MAXN << 2] , psX[MAXN] , psY[MAXN];
ll seg[MAXN << 2];
vector<int> compressX = {-1} , compressY = {-1} , vec[MAXN];

void build(int k , int id = 1 , int l = 0 , int r = MAXN){
	lz[id] = 0;
	if(r - l == 1){
		seg[id] = 1ll * k * psY[l];
		return;
	}
	int mid = l + r >> 1;
	build(k , lc , l , mid);
	build(k , rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

void shift(int id){
	seg[lc] += lz[id]; lz[lc] += lz[id];
	seg[rc] += lz[id]; lz[rc] += lz[id];
	lz[id] = 0;
}

void add(int ql , int qr , int x , int id = 1 , int l = 0 , int r = MAXN){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		lz[id] += x;
		seg[id] += x;
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	add(ql , qr , x , lc , l , mid);
	add(ql , qr , x , rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

int check(int k){
	build(k);
	for(int i = MAXN - 1 ; i >= 0 ; i--){
		if(1ll * k * psX[i] >= n)	return 1;
		for(int j : vec[i]){
			if(1ll * k * psY[j] < n)
				add(0 , j + 1 , -1);
//			cout << "new " << i << ' ' << j << endl;
		}
//		cout << "check " << i << ' ' << seg[1] << ' ' << valX[i] << ' ' << valY[i] << endl;
		if(seg[1] + 1ll * k * psX[i] < 0)	return 0;
	}
	return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = T;
	for(int i = 0 ; i < T ; i++){
//		compressX.push_back(W[i]);
//		compressY.push_back(S[i]);
	}
	for(int i = 0 ; i < A ; i++){
		compressX.push_back(X[i] - 1);
		compressX.push_back(X[i]);
	}
	for(int i = 0 ; i < B ; i++){
		compressY.push_back(Y[i] - 1);
		compressY.push_back(Y[i]);
	}
	sort(all(compressX)); compressX.resize(unique(all(compressX)) - compressX.begin());
	sort(all(compressY)); compressY.resize(unique(all(compressY)) - compressY.begin());
	for(int i = 0 ; i < T ; i++){
		W[i] = lower_bound(all(compressX) , W[i]) - compressX.begin();
		S[i] = lower_bound(all(compressY) , S[i]) - compressY.begin();
//		cout << W[i] << ' ' << S[i] << endl;
		vec[W[i]].push_back(S[i]);
	}
	for(int i = 0 ; i < A ; i++){
		X[i] = lower_bound(all(compressX) , X[i]) - compressX.begin();
//		cout << X[i] << endl;
//		if(X[i] == 0)	return 0;
		psX[X[i] - 1]++;
	}
//	cout << endl;
	for(int i = 0 ; i < B ; i++){
		Y[i] = lower_bound(all(compressY) , Y[i]) - compressY.begin();
//		cout << Y[i] << endl;
//		if(Y[i] == 0)	return 0;
		psY[Y[i] - 1]++;
	}
	for(int i = MAXN - 2 ; i >= 0 ; i--){
		psX[i] += psX[i + 1];
		psY[i] += psY[i + 1];
	}
	int l = 0 , r = MAXN * 10;
	while(r - l > 1){
		int mid = l + r >> 1;
		if(check(mid))	r = mid;
		else	l = mid;
	}
	return (r == MAXN * 10 ? -1 : r);
}

Compilation message (stderr)

robots.cpp: In function 'void build(int, int, int, int)':
robots.cpp:24:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int mid = l + r >> 1;
      |            ~~^~~
robots.cpp: In function 'void add(int, int, int, int, int, int)':
robots.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |  int mid = l + r >> 1;
      |            ~~^~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:106:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |   int mid = l + r >> 1;
      |             ~~^~~

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