Submission #152298

#	Time	Username	Problem	Language	Result	Execution time	Memory
152298		Mahotsukai	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	3039 ms	368688 KiB

squad

#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef vector<string> vs;
template<class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &P){
	in >> P.first >> P.second;
	return in;
}
template<class T1, class T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &P){
	out << "(" << P.first << ", " << P.second << ")";
	return out;
}
template<class T>
istream &operator>>(istream &in, vector<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}
template<class T>
ostream &operator<<(ostream &out, const vector<T> &arr){
	for(auto &x: arr) out << x << ' '; cout << "\n";
	return out;
}
template<class T>
istream &operator>>(istream &in, deque<T> &arr){
	for(auto &x: arr) in >> x;
	return in;
}
template<class T>
ostream &operator<<(ostream &out, const deque<T> &arr){
	for(auto &x: arr) out << x << ' '; cout << "\n";
	return out;
}

struct point{
	ll x, y;
	point(pll p): x(p.first), y(p.second){}
	point(ll x = 0, ll y = 0): x(x), y(y){}
	bool operator<(const point &other) const{
		return x < other.x || (x == other.x && y < other.y);
	}
	point operator+(const point &other) const{
		return point(x + other.x, y + other.y);
	}
	point operator+=(const point &other){
		return *this = *this + other;
	}
	point operator-(const point &other) const{
		return point(x - other.x, y - other.y);
	}
	point operator-=(const point &other){
		return *this = *this - other;
	}
	ll operator*(const point &other) const{
		return x * other.x + y * other.y;
	}
};
istream &operator>>(istream &in, point &p){
	cin >> p.x >> p.y;
	return in;
}
ostream &operator<<(ostream &out, const point &p){
	cout << "(" << p.x << ", " << p.y << ")";
	return out;
}
ll ori(const point &p, const point &q, const point &r){
	return p.x * q.y + q.x * r.y + r.x * p.y - p.y * q.x - q.y * r.x - r.y * p.x;
}
struct convhull{
	int N, R;
	vector<point> ch;
	convhull(vector<point> arr = vector<point>(), bool sorted = false){
		if(arr.size() <= 1){
			ch = arr;
			N = R = arr.size(), R --;
			return;
		}
		if(!sorted) sort(arr.begin(), arr.end());
		vector<point> upper, lower;
		point p = arr.front(), q = arr.back();
		upper.push_back(p), lower.push_back(p);
		for(int i = 1; i < arr.size(); i ++){
			if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
				while(upper.size() >= 2 && ori(upper[upper.size() - 2], upper[upper.size() - 1], arr[i]) >= 0){
					upper.pop_back();
				}
				upper.push_back(arr[i]);
			}
			if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
				while(lower.size() >= 2 && ori(lower[lower.size() - 2], lower[lower.size() - 1], arr[i]) <= 0){
					lower.pop_back();
				}
				lower.push_back(arr[i]);
			}
		}
		for(int i = 0; i < lower.size(); i ++) ch.push_back(lower[i]);
		for(int i =	upper.size() - 2; i; i --) ch.push_back(upper[i]);
		N = ch.size(), R = lower.size() - 1;
	}
	vector<point> linearize() const{
		if(N <= 1) return ch;
		int i = 0, j = N - 1;
		vector<point> res;
		while(i != R && j != R){
			if(ch[i] < ch[j]) res.push_back(ch[i ++]);
			else res.push_back(ch[j --]);
		}
		while(i < R) res.push_back(ch[i ++]);
		while(j > R) res.push_back(ch[j --]);
		res.push_back(ch[R]);
		return res;
	}
	int max_element(ll x, ll y){
		point p(x, y);
		int l = R, r = N;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * ch[m1] <= p * ch[m2] ? l = m1 : r = m2;
		}
		int res = l;
		for(int i = l + 1; i < r; i ++) if(p * ch[res] < p * ch[i]) res = i;
		return res;
	}
	int min_element(ll x, ll y){
		point p(x, y);
		int l = 0, r = R + 1;
		while(r - l > 3){
			int m1 = (2 * l + r) / 3, m2 = (l + 2 * r) / 3;
			p * ch[m1] >= p * ch[m2] ? l = m1 : r = m2;
		}
		int res = l;
		for(int i = l + 1; i < r; i ++) if(p * ch[res] > p * ch[i]) res = i;
		return res;
	}
	convhull operator+(const convhull &other) const{
		if(!this->N || !other.N) return convhull();
		convhull temp1(*this), temp2(other), temp;
		for(int i = 0; i + 1 < temp1.N; i ++) temp1.ch[i] = this->ch[i + 1] - this->ch[i];
		for(int i = 0; i + 1 < temp2.N; i ++) temp2.ch[i] = other.ch[i + 1] - other.ch[i];
		temp1.ch.back() = this->ch.front() - this->ch.back();
		temp2.ch.back() = other.ch.front() - other.ch.back();
		int i = 0, j = 0;
		function<bool(point, point)> cmp = [&](point p, point q){
			int typep = 1, typeq = 1;
			if(p.x > 0 || !p.x && p.y <= 0) typep = 0;
			if(q.x > 0 || !q.x && q.y <= 0) typeq = 0;
			if(typep != typeq) return typep < typeq;
			return ori(p, q, point(0, 0)) >= 0;
		};
		while(i < temp1.N && j < temp2.N){
			if(cmp(temp1.ch[i], temp2.ch[j])) temp.ch.push_back(temp1.ch[i ++]);
			else temp.ch.push_back(temp2.ch[j ++]);
		}
		for(; i < temp1.N; i ++) temp.ch.push_back(temp1.ch[i]);
		for(; j < temp2.N; j ++) temp.ch.push_back(temp2.ch[j]);
		convhull res;
		res.ch.push_back(this->ch[0] + other.ch[0]);
		for(int i = 0; i + 1 < temp.ch.size(); i ++){
			res.ch.push_back(res.ch.back() + temp.ch[i]);
		}
		res.N = res.ch.size();
		res.R = std::max_element(all(res.ch)) - res.ch.begin();
		return res;
	}
	convhull operator^(const convhull &other) const{
		if(!this->N) return other;
		if(!other.N) return *this;
		auto temp1 = this->linearize(), temp2 = other.linearize();
		vector<point> res(temp1.size() + temp2.size());
		merge(all(temp1), all(temp2), res.begin());
		return convhull(res, true);
	}
	convhull operator-() const{
		auto res = *this;
		for(auto &p: res.ch) p = point(-p.x, -p.y);
		res.R = std::max_element(all(res.ch)) - res.ch.begin();
		return res;
	}
};
convhull c;
typedef pair<convhull, convhull> pcc;
void Init(vi a, vi d, vi p){
	int n = a.size();
	vector<vector<point>> data(2, vector<point>(n));
	for(int i = 0; i < n; i ++) data[0][i] = point(a[i], p[i]), data[1][i] = point(d[i], p[i]);
	function<pcc(int, int)> solve = [&](int l, int r){
		if(r - l == 1){
			return pcc(convhull({data[0][l]}), convhull({data[1][l]}));
		}
		int m = l + r >> 1;
		auto p = solve(l, m), q = solve(m, r);
		auto res = p.first + q.second;
		for(auto &x: res.ch) c.ch.push_back(x);
		res = p.second + q.first;
		for(auto &x: res.ch) c.ch.push_back(x);
		return pcc(p.first^q.first, p.second^q.second);
	};
	solve(0, n);
	c = convhull(c.ch);
}
ll BestSquad(int x, int y){
	int p = c.max_element(x, y);
	return point(x, y) * c.ch[p];
}
/*
6 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 1 5
2 1 6
100 

4 
3 1 4 
2 3 3 
2 1 6 
4 4 1 
2 
1 3 
3 1 
*/

//////////////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                                  //
//                                                                                                  //
//                                              _____________                                       //
//             ++++++++++                ___------------------\\\\                                  //
//           +++`+``+`+`++++        ///`````````````````````````````\\\                             //
//           ++`+`+``+++`++++  /////```````````````````````````````````\\                           //
//           +++`++`+`+``+++/////`````````````````````````````````````````\\                        //
//             +++`++`+``+///```````````|```````````````````````````````````\\                      //
//          ____++++/++++/`````````````/````````|````````|```````````````````\\                     //
//        /  /  / |    //``````````````|````````|```````|````````|````````````\\                    //
//       /  /  /  | ///````````/```````|```````||```````|````````|``````\```````\\                  //
//       | /  /   |///`````````|``````/````````|````````|````````|```````|```````\\                 //
//       |/   |   |//``|```````|``````|````````|`````````|```````|```````|````````\\                //
//       /\___|__//`|``|```````|`    |      ``:|````````|:```````|```````|```|`````|                //
//      /     /  /``|``|``````|/     |        :|     ```:|```````|```````|``++````++                //
//     /     / //```|``|``````|      |        |:        :|    ```|```````|```++``++`\               //
//     |    /  /````|``|``````/    _.::::.    |          |      |    ````|```|`++`\`|               //
//     |   /   |````|``|`````|            `                    |       ``|```++``++`|               //
//     |  /    |````|``|`````|                                 :         |``++````++|               //
//     | /     /````|``|`````|                              _.-:::.      |..`|``.`|.|               //
//     |/     /`````|``|`````|                                     `     |```|````|`|               //
//    /|      |`````|``|`````|                    :'                    .|```|````|.|               //
//   / |      |`````|``|`````|                                         /|-|``|````|`|               //
//  /  |      |`````|```\````|                                        / ||```|````|``\              //
// /   |      |`````|````|```|::                                    /_| ||```|````|``|              //
//            |`````|````|```|:|:.        `.._                    .\___/:|```|````|``|              //
//            |`````\````|```|:|::-          ``:::....           -:|:|:::|```|````|``|              //
//            |``````|```|```|:|::`|.                          .:::|:|:::|```|````|``|              //
//             \`````|```|```|:|::/|--.                     .`:|:::|:|:::/```|````|``|              //
//              |````|```|```\:|:|:|-----             _..-:|:|:|:::|:|::|````|````|`/               //
//              |````|```|````\|:|:|-------.____.....------|/::|:::|:|::|````|````|`|               //
//              |````|```|\````\:|/\___________    ________/\--\:::|:|::|````/````|`|               //
//              |````\```| \```|:/-------------\  /----------\``\::|:|::|```/`````|`|               //
//              |`````|``|  \``|/---------------\/------------\_________|```|`````|`|               //
//                                                                                                  //
//////////////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                                  //
//                                        Created by Aeren                                          //
//                                                                                                  //
//////////////////////////////////////////////////////////////////////////////////////////////////////

Compilation message (stderr)

squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
squad.cpp:31:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:31:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto &x: arr) out << x << ' '; cout << "\n";
                                     ^~~~
squad.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::deque<_Tp>&)':
squad.cpp:41:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(auto &x: arr) out << x << ' '; cout << "\n";
  ^~~
squad.cpp:41:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(auto &x: arr) out << x << ' '; cout << "\n";
                                     ^~~~
squad.cpp: In constructor 'convhull::convhull(std::vector<point>, bool)':
squad.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < arr.size(); i ++){
                  ~~^~~~~~~~~~~~
squad.cpp:93:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == arr.size() - 1 || ori(p, arr[i], q) < 0){
       ~~^~~~~~~~~~~~~~~~~
squad.cpp:99:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i == arr.size() - 1 || ori(p, arr[i], q) > 0){
       ~~^~~~~~~~~~~~~~~~~
squad.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < lower.size(); i ++) ch.push_back(lower[i]);
                  ~~^~~~~~~~~~~~~~
squad.cpp: In lambda function:
squad.cpp:155:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(p.x > 0 || !p.x && p.y <= 0) typep = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp:156:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if(q.x > 0 || !q.x && q.y <= 0) typeq = 0;
                  ~~~~~^~~~~~~~~~~
squad.cpp: In member function 'convhull convhull::operator+(const convhull&) const':
squad.cpp:168:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i + 1 < temp.ch.size(); i ++){
                  ~~~~~~^~~~~~~~~~~~~~~~
squad.cpp: In lambda function:
squad.cpp:200:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~

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