Submission #150915

#	Time	Username	Problem	Language	Result	Execution time	Memory
150915		gs18103	Organizing the Best Squad (FXCUP4_squad)	C++17	28 / 100	597 ms	56320 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
#define g(tp, x) get<x>(tp)
#define eb emplace_back
#define all(v) (v).begin(), (v).end()

using namespace std;
typedef long long ll;
typedef tuple <ll, ll, int> tp3;

vector <tp3> p1, p2, ch1, chs1, ch2, chs2, temp;
bool chk1[303030], chk2[303030];

bool ccw(tp3 a, tp3 b, tp3 c) {
	return (g(b, 0) - g(a, 0)) * (g(c, 1) - g(a, 1)) - 
			(g(c, 0) - g(a, 0)) * (g(b, 1) - g(a, 1)) >= 0;
}

void Init(vector<int> A, vector<int> D, vector<int> P){
	int n = A.size();
	for(int i = 0; i < n; i++) {
		p1.eb((ll)A[i], (ll)P[i], i);
		p2.eb((ll)D[i], (ll)P[i], i);
	}

	sort(all(p1), [](tp3 a, tp3 b) {
		if(g(a, 0) == g(b, 0)) return g(a, 1) > g(b, 1);
		else return a < b;
	});

	for(int i = 0; i < n; i++) {
		while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p1[i], 1)) {
			temp.pop_back();
		}
		temp.eb(p1[i]);
	}
	for(int i = 0; i < temp.size(); i++) {
		while(ch1.size() >= 2 && ccw(ch1[ch1.size()-2], ch1[ch1.size()-1], temp[i])) {
			ch1.pop_back();
		}
		ch1.eb(temp[i]);
	}

	for(int i = 0; i < ch1.size(); i++) chk1[g(ch1[i], 2)] = true;
	temp.clear();

	for(int i = 0; i < n; i++) {
		if(chk1[g(p1[i], 2)]) continue;
		while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p1[i], 1)) {
			temp.pop_back();
		}
		temp.eb(p1[i]);
	}
	for(int i = 0; i < temp.size(); i++) {
		while(chs1.size() >= 2 && ccw(chs1[chs1.size()-2], chs1[chs1.size()-1], temp[i])) {
			chs1.pop_back();
		}
		chs1.eb(temp[i]);
	}
	temp.clear();



	sort(all(p2), [](tp3 a, tp3 b) {
		if(g(a, 0) == g(b, 0)) return g(a, 1) > g(b, 1);
		else return a < b;
	});

	for(int i = 0; i < n; i++) {
		while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p2[i], 1)) {
			temp.pop_back();
		}
		temp.eb(p2[i]);
	}
	for(int i = 0; i < temp.size(); i++) {
		while(ch2.size() >= 2 && ccw(ch2[ch2.size()-2], ch2[ch2.size()-1], temp[i])) {
			ch2.pop_back();
		}
		ch2.eb(temp[i]);
	}

	for(int i = 0; i < ch2.size(); i++) chk2[g(ch2[i], 2)] = true;
	temp.clear();

	for(int i = 0; i < n; i++) {
		if(chk2[g(p2[i], 2)]) continue;
		while(!temp.empty() && g(temp[temp.size()-1], 1) < g(p2[i], 1)) {
			temp.pop_back();
		}
		temp.eb(p2[i]);
	}
	for(int i = 0; i < temp.size(); i++) {
		while(chs2.size() >= 2 && ccw(chs2[chs2.size()-2], chs2[chs2.size()-1], temp[i])) {
			chs2.pop_back();
		}
		chs2.eb(temp[i]);
	}
}

long long BestSquad(int X, int Y){
	ll ma1 = 0, ma2 = 0, md1 = 0, md2 = 0;
	int ia = 0, id = 0;
	int lb, ub;

	lb = 0, ub = ch1.size()-2;
	while(lb < ub) {
		int m = (lb + ub + 1) >> 1;
		if((g(ch1[m+1], 1) - g(ch1[m], 1)) * Y >
			-X * (g(ch1[m+1], 0) - g(ch1[m], 0))) lb = m;
		else ub = m - 1;
	}
	ia = lb;
	ma1 = max(ma1, X * g(ch1[ia], 0) + Y * g(ch1[ia], 1));
	if(ia > 0) ma2 = max(ma2, X * g(ch1[ia-1], 0) + Y * g(ch1[ia-1], 1));
	if(ia+1 < ch1.size()) {
		ma2 = max(ma2, X * g(ch1[ia+1], 0) + Y * g(ch1[ia+1], 1));
		if(ma2 > ma1) swap(ma1, ma2), ia++;
	}
	if(!chs1.empty()) {
		lb = 0, ub = chs1.size()-2;
		while(lb < ub) {
			int m = (lb + ub + 1) >> 1;
			if((g(chs1[m+1], 1) - g(chs1[m], 1)) * Y >
				-X * (g(chs1[m+1], 0) - g(chs1[m], 0))) lb = m;
			else ub = m - 1;
		}
		ma2 = max(ma2, X * g(chs1[lb], 0) + Y * g(chs1[lb], 1));
		if(lb+1 < chs1.size()) ma2 = max(ma2, X * g(chs1[lb+1], 0) + Y * g(chs1[lb+1], 1));
	}

	lb = 0, ub = ch2.size()-2;
	while(lb < ub) {
		int m = (lb + ub + 1) >> 1;
		if((g(ch2[m+1], 1) - g(ch2[m], 1)) * Y >
			-X * (g(ch2[m+1], 0) - g(ch2[m], 0))) lb = m;
		else ub = m - 1;
	}
	id = min(lb, (int)ch2.size()-1);
	md1 = max(md1, X * g(ch2[id], 0) + Y * g(ch2[id], 1));
	if(id > 0) md2 = max(md2, X * g(ch2[id-1], 0) + Y * g(ch2[id-1], 1));
	if(id+1 < ch2.size()){
		md2 = max(md2, X * g(ch2[id+1], 0) + Y * g(ch2[id+1], 1));
		if(md2 > md1) swap(md1, md2), id++;
	} 
	if(!chs2.empty()) {
	lb = 0, ub = chs2.size()-2;
		while(lb < ub) {
			int m = (lb + ub + 1) >> 1;
			if((g(chs2[m+1], 1) - g(chs2[m], 1)) * Y >
				-X * (g(chs2[m+1], 0) - g(chs2[m], 0))) lb = m;
			else ub = m - 1;
		}
		lb = min(lb, (int)chs2.size()-1);
		md2 = max(md2, X * g(chs2[lb], 0) + Y * g(chs2[lb], 1));
		if(lb+1 < chs2.size()) ma2 = max(ma2, X * g(chs2[lb+1], 0) + Y * g(chs2[lb+1], 1));
	}

	if(g(ch1[ia], 2) != g(ch2[id], 2)) return ma1 + md1;
	else return max(ma1 + md2, ma2 + md1);
}

Compilation message (stderr)

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < temp.size(); i++) {
                 ~~^~~~~~~~~~~~~
squad.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ch1.size(); i++) chk1[g(ch1[i], 2)] = true;
                 ~~^~~~~~~~~~~~
squad.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < temp.size(); i++) {
                 ~~^~~~~~~~~~~~~
squad.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < temp.size(); i++) {
                 ~~^~~~~~~~~~~~~
squad.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ch2.size(); i++) chk2[g(ch2[i], 2)] = true;
                 ~~^~~~~~~~~~~~
squad.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < temp.size(); i++) {
                 ~~^~~~~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:115:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ia+1 < ch1.size()) {
     ~~~~~^~~~~~~~~~~~
squad.cpp:128:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lb+1 < chs1.size()) ma2 = max(ma2, X * g(chs1[lb+1], 0) + Y * g(chs1[lb+1], 1));
      ~~~~~^~~~~~~~~~~~~
squad.cpp:141:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(id+1 < ch2.size()){
     ~~~~~^~~~~~~~~~~~
squad.cpp:155:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lb+1 < chs2.size()) ma2 = max(ma2, X * g(chs2[lb+1], 0) + Y * g(chs2[lb+1], 1));
      ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 19
• Subtask 2: 28 / 28
• Subtask 3: 0 / 53