Submission #150523

#	Time	Username	Problem	Language	Result	Execution time	Memory
150523		본인 하지만 안 어림 ㅋㅋ (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1112 ms	53136 KiB

squad

#include "squad.h"
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> p;
typedef pair<p, int> pp;

pp a[300003];
vector<pp> AA, DD;
vector<p> AAA[300003], DDD[300003];

inline long long ccw(p &u, p &v, p &w) {
	return (long long)(w.first - u.first) * (v.second - u.second) - (long long)(w.second - u.second) * (v.first - u.first);
}

inline long long ccw(pp &u, pp &v, pp &w) {
	return ccw(u.first, v.first, w.first);
}

inline void create(int N, vector<int> &A, vector<int> &P, vector<pp> &r, vector<p> *s) {
	int i, j;
	for (i = 0; i < N; i++) {
		a[i].first.first = A[i];
		a[i].first.second = P[i];
		a[i].second = i;
	}
	sort(a, a + N);
	for (i = 0; i < N; i++) {
		while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
		r.push_back(a[i]);
	}
	for (i = 0; i < r.size(); i++) {
		auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
		auto &t = s[r[i].second];
		for (; L < R; L++) {
			if (*L == r[i]) continue;
			while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
			t.push_back(L->first);
		}
	}
}

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int N = A.size();
	create(N, A, P, AA, AAA);
	create(N, D, P, DD, DDD);
	//for (auto t : AA) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
	//for (auto t : DD) printf("%d %d %d\n", t.first.first, t.first.second, t.second); puts("");
	//for (int i = 0; i < N; i++) if (!AAA[i].empty()) { printf("%d : ", i); for (auto t : AAA[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
	//for (int i = 0; i < N; i++) if (!DDD[i].empty()) { printf("%d : ", i); for (auto t : DDD[i]) printf("(%d %d) ", t.first, t.second); puts(""); }
}

inline pp bs(vector<pp> &AA, long long X, long long Y) {
	int L = 0, R = AA.size() - 1;
	while (L < R) {
		int M = L + R >> 1;
		if (X * AA[M].first.first + Y * AA[M].first.second < X * AA[M + 1].first.first + Y * AA[M + 1].first.second) L = M + 1;
		else R = M;
	}
	return AA[L];
}

inline p bs(vector<p> &AAA, long long X, long long Y) {
	int L = 0, R = AAA.size() - 1;
	while (L < R) {
		int M = L + R >> 1;
		if (X * AAA[M].first + Y * AAA[M].second < X * AAA[M + 1].first + Y * AAA[M + 1].second) L = M + 1;
		else R = M;
	}
	return AAA[L];
}

long long BestSquad(int X, int Y){
	auto A = bs(AA, X, Y), D = bs(DD, X, Y);
	//printf("%d %d %d, %d %d %d\n", A.first.first, A.first.second, A.second, D.first.first, D.first.second, D.second);
	if (A.second != D.second) return 1ll * X * (A.first.first + D.first.first) + 1ll * Y * (A.first.second + D.first.second);
	auto A2 = bs(AAA[A.second], X, Y), D2 = bs(DDD[D.second], X, Y);
	return max(
		1ll * X * (A.first.first + D2.first) + 1ll * Y * (A.first.second + D2.second),
		1ll * X * (D.first.first + A2.first) + 1ll * Y * (D.first.second + A2.second)
	);
}

Compilation message (stderr)

squad.cpp: In function 'void create(int, std::vector<int>&, std::vector<int>&, std::vector<std::pair<std::pair<int, int>, int> >&, std::vector<std::pair<int, int> >*)':
squad.cpp:31:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while (!r.empty() && r[r.size() - 1].first.first <= a[i].first.first && r[r.size() - 1].first.second <= a[i].first.second || r.size() > 1 && ccw(r[r.size() - 2], r[r.size() - 1], a[i]) <= 0) r.pop_back();
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < r.size(); i++) {
              ~~^~~~~~~~~~
squad.cpp:35:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   auto L = i ? lower_bound(a, a + N, r[i - 1]) : a, R = i + 1 < r.size() ? upper_bound(a, a + N, r[i + 1]) : a + N;
                                                         ~~~~~~^~~~~~~~~~
squad.cpp:39:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while (!t.empty() && t[t.size() - 1].first <= L->first.first && t[t.size() - 1].second <= L->first.second || t.size() > 1 && ccw(t[t.size() - 2], t[t.size() - 1], L->first) <= 0) t.pop_back();
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
squad.cpp:23:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
squad.cpp: In function 'pp bs(std::vector<std::pair<std::pair<int, int>, int> >&, long long int, long long int)':
squad.cpp:58:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~
squad.cpp: In function 'p bs(std::vector<std::pair<int, int> >&, long long int, long long int)':
squad.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~

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