oj.uz

Submission #148144

# Submission time Handle Problem Language Result Execution time Memory
148144 2019-08-31T14:48:00 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1070 ms 91272 KB 
#include <bits/stdc++.h>
#include "squad.h"

using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

struct point {
	int x, y, idx;
	ll calc(ll X, ll Y) { return X * x + Y * y; }
};
point operator-(point a, point b) { return {a.x - b.x, a.y - b.y, -1}; }
ll operator/(point a, point b) { return (ll)a.x * b.y - (ll)a.y * b.x; }

struct hull {
	vector <point> L, cvx;
	vector <vector <point> > Area, CX2;
	void Init(vector <int> X, vector <int> Y) {
		int N = szz(X);
		rep(i, N) {
			L.pb({X[i], Y[i], i});
		}
		sort(all(L), [&](point a, point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
		vector <point> pl;
		for(int i=0;i<N;i++) {
			while(szz(pl) && pl.back().y <= L[i].y) pl.pop_back();
			pl.pb(L[i]);
		}
		for(point p : pl) {
			while(szz(cvx) > 1 && (cvx.back() - cvx[szz(cvx)-2]) / (p - cvx.back()) >= 0) cvx.pop_back();
			cvx.pb(p);
		}
		int m = szz(cvx);
		Area.resize(m);
		for(int i=0;i<N;i++) {
			int v = (int)(lower_bound(all(cvx), L[i], [&](point a, point b) {
				return a.x < b.x;
			}) - cvx.begin());
			if(cvx[v].idx == L[i].idx) continue;
			Area[v].pb(L[i]);
		}
		CX2.resize(m);
		for(int i=0;i<m;i++) {
			if(i) CX2[i].pb(cvx[i-1]);
			for(auto &p : Area[i]) CX2[i].pb(p);
			if(i<m-1) {
				for(auto &p : Area[i+1]) CX2[i].pb(p);
				CX2[i].pb(cvx[i+1]);
			}
			vector <point> temp;
			for(auto p : CX2[i]) {
				while(szz(temp) > 1 && (temp.back() - temp[szz(temp)-2]) / (p - temp.back()) >= 0) temp.pop_back();
				temp.pb(p);
			}
			swap(CX2[i], temp);
		}
	}
	pair<point, point> Query(ll X, ll Y) {
		int low = 0, high = szz(cvx) - 2, res = 0;
		ll h1 = cvx[0].calc(X, Y);
		while(low <= high) {
			int mid = (low + high) >> 1;
			ll c1 = cvx[mid].calc(X, Y);
			ll c2 = cvx[mid+1].calc(X, Y);
			if(c1 < c2) {
				if(h1 < c2) h1 = c2, res = mid + 1;
				low = mid + 1;
			}
			else {
				if(h1 < c1) h1 = c1, res = mid;
				high = mid - 1;
			}
		}
		point p1 = cvx[res];
		int R1 = res;
		low = 0, high = szz(CX2[res]) - 2, res = 0;
		h1 = CX2[R1][0].calc(X, Y);
		while(low <= high) {
			int mid = (low + high) >> 1;
			ll c1 = CX2[R1][mid].calc(X, Y);
			ll c2 = CX2[R1][mid+1].calc(X, Y);
			if(c1 < c2) {
				if(h1 < c2) h1 = c2, res = mid + 1;
				low = mid + 1;
			}
			else {
				if(h1 < c1) h1 = c1, res = mid;
				high = mid - 1;
			}
		}
		point p2 = CX2[R1][res];

		return make_pair(p1, p2);
	}
} H[2];

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	H[0].Init(A, P);
	H[1].Init(D, P);
}

long long BestSquad(int X, int Y){
	auto v1 = H[0].Query(X, Y);
	auto v2 = H[1].Query(X, Y);
	ll res = 0;
	for(auto p : {v1.Fi, v1.Se}) {
		for(auto q : {v2.Fi, v2.Se}) {
			if(p.idx != q.idx) {
				res = max(res, p.calc(X,Y) + q.calc(X,Y));
			}
		}
	}
	return res;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 301 ms 40108 KB Output is correct
4 Correct 307 ms 43884 KB Output is correct
5 Correct 31 ms 5712 KB Output is correct
6 Correct 478 ms 83048 KB Output is correct
7 Correct 473 ms 83020 KB Output is correct
8 Correct 471 ms 83156 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 445 ms 45284 KB Output is correct
4 Correct 465 ms 48688 KB Output is correct
5 Correct 26 ms 3152 KB Output is correct
6 Correct 713 ms 66264 KB Output is correct
7 Correct 716 ms 66228 KB Output is correct
8 Correct 700 ms 66132 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 301 ms 40108 KB Output is correct
4 Correct 307 ms 43884 KB Output is correct
5 Correct 31 ms 5712 KB Output is correct
6 Correct 478 ms 83048 KB Output is correct
7 Correct 473 ms 83020 KB Output is correct
8 Correct 471 ms 83156 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 445 ms 45284 KB Output is correct
12 Correct 465 ms 48688 KB Output is correct
13 Correct 26 ms 3152 KB Output is correct
14 Correct 713 ms 66264 KB Output is correct
15 Correct 716 ms 66228 KB Output is correct
16 Correct 700 ms 66132 KB Output is correct
17 Correct 82 ms 5492 KB Output is correct
18 Correct 7 ms 888 KB Output is correct
19 Correct 502 ms 53496 KB Output is correct
20 Correct 516 ms 51896 KB Output is correct
21 Correct 40 ms 4508 KB Output is correct
22 Correct 1012 ms 91164 KB Output is correct
23 Correct 1070 ms 91236 KB Output is correct
24 Correct 1024 ms 91272 KB Output is correct