#include "squad.h"
#include<vector>
#include<algorithm>
#include<assert.h>
#include<utility>
using namespace std;
typedef long long LL;
//StaticCHT<LL> cht;
//cht.InsertLine({ id, m, c });
//auto ret = cht.SlidingEval(x);
template<class T = LL>
struct Line {
int id;
// y = mx + c
T m, c;
// The line starts from start_x.
static const LL MIN_START_X = 0;
long double start_x;
LL Eval(LL x) { return m * x + c; }
long double Eval(long double x) { return m * x + c; }
long double Intersect(const Line& other) {
// mx + c = other.m * x + other.c
long double num = other.c - c;
long double den = m - other.m;
assert(m != other.m);
return num / den;
}
};
template<class T = LL>
struct StaticCHT {
static const int MIN_TYPE = 0;
static const int MAX_TYPE = 1;
int type = MAX_TYPE;
// Stores convex hull lines.
vector<Line<T>> ch;
// Used if the query x is increasing.
// id of the current segment.
int id = 0;
void InsertLine(Line<T> cur) {
int sz = ch.size();
if (sz) assert(type == MAX_TYPE || (ch[sz - 1].m > cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c >= cur.c)));
if (sz) assert(type == MIN_TYPE || (ch[sz - 1].m < cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c <= cur.c)));
if (sz) {
if (ch[sz - 1].c == cur.c && ch[sz - 1].m == cur.m) return;
}
while (sz > 1) {
double left_side = (LL(ch[sz - 1].c - ch[sz - 2].c)) * (ch[sz - 2].m - cur.m);
double right_side = (LL(ch[sz - 2].m - ch[sz - 1].m)) * (cur.c - ch[sz - 2].c);
if ((left_side >= right_side)) {
ch.pop_back();
sz--;
}
else break;
}
if (!sz) cur.start_x = Line<T>::MIN_START_X;
else cur.start_x = ch[sz - 1].Intersect(cur);
ch.push_back(cur);
}
pair<int, T> SlidingEval(T x) {
// There should be at least one element.
assert(SZ(ch) > 0);
// May be ch was updated by the time?
id = MIN(id, SZ(ch));
while (id + 1 < SZ(ch) && ((type == MIN_TYPE && ch[id].Eval(x) > ch[id + 1].Eval(x)) ||
(type == MAX_TYPE && ch[id].Eval(x) < ch[id + 1].Eval(x)))) {
id++;
}
return { ch[id].id, ch[id].Eval(x) };
}
vector<int> Eval(T x, int qmode) {
if (ch.size() == 0) return {};
int lo = 0, hi = (int)(ch.size()) - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (ch[mid].start_x > x) hi = mid - 1;
else lo = mid;
}
vector<int> V;
if (qmode && lo) V.push_back(ch[lo - 1].id);
V.push_back(ch[lo].id);
if (qmode && lo + 1 < ch.size()) V.push_back(ch[lo + 1].id);
return V;
}
};
StaticCHT<LL> Atree1, Atree2;
StaticCHT<LL> Dtree1, Dtree2;
int Amark[300005], Dmark[300005];
vector<int> A, D, P;
struct Person {
int id, p, z;
};
bool operator< (Person A, Person B) {
return A.p < B.p;
}
vector<Person> Attack, Defence;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
int n = A.size();
::A = A;
::D = D;
::P = P;
for (int i = 0; i < n; i++) {
Attack.push_back({ i, P[i], A[i] });
Defence.push_back({ i, P[i], D[i] });
}
sort(Attack.begin(), Attack.end());
sort(Defence.begin(), Defence.end());
for (int i = 0; i < n; i++) {
Atree1.InsertLine({ Attack[i].id, Attack[i].p, Attack[i].z });
Dtree1.InsertLine({ Defence[i].id, Defence[i].p, Defence[i].z });
}
for (auto& p : Atree1.ch) {
Amark[p.id] = 1;
}
for (auto& p : Dtree1.ch) {
Dmark[p.id] = 1;
}
for (int i = 0; i < n; i++) {
if (!Amark[Attack[i].id]) Atree2.InsertLine({ Attack[i].id, Attack[i].p, Attack[i].z });
if (!Dmark[Defence[i].id]) Dtree2.InsertLine({ Defence[i].id, Defence[i].p, Defence[i].z });
}
}
#define MAX(A, B) ((A) > (B) ? (A) : (B))
long long BestSquad(int X, int Y){
vector<int> AX = Atree1.Eval(Y, 1); vector<int> tx = Atree2.Eval(Y, 0);
if (tx.size()) AX.push_back(tx[0]);
vector<int> AY = Dtree1.Eval(Y, 1); vector<int> ty = Dtree2.Eval(Y, 0);
if (ty.size()) AY.push_back(ty[0]);
LL ret = 0;
for (int a : AX) for (int b : AY) {
if (a != b) {
ret = MAX(ret, (1LL * X) * (A[a] + D[b]) + (1LL * Y) * (P[a] + P[b]));
}
}
return ret;
}
Compilation message
squad.cpp: In instantiation of 'std::vector<int> StaticCHT<T>::Eval(T, int) [with T = long long int]':
squad.cpp:135:35: required from here
squad.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (qmode && lo + 1 < ch.size()) V.push_back(ch[lo + 1].id);
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
432 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
432 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
