結果
| 問題 | No.703 ゴミ拾い Easy |
| ユーザー |
 ei1333333
|
| 提出日時 | 2018-06-15 22:53:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 152 ms / 1,500 ms |
| コード長 | 4,675 bytes |
| コンパイル時間 | 2,340 ms |
| コンパイル使用メモリ | 200,912 KB |
| 最終ジャッジ日時 | 2025-01-05 14:02:30 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:147:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
147 | scanf("%lld", &N);
| ~~~~~^~~~~~~~~~~~
main.cpp:148:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
148 | for(int i = 0; i < N; i++) scanf("%lld", &A[i]);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:149:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
149 | for(int i = 0; i < N; i++) scanf("%lld", &X[i]);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:150:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
150 | for(int i = 0; i < N; i++) scanf("%lld", &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp: In member function ‘bool ConvexHullDynamic::Line::operator<(const ConvexHullDynamic::Line&) const’:
main.cpp:42:5: warning: control reaches end of non-void function [-Wreturn-type]
42 | }
| ^
ソースコード
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 INF = 1LL << 58;
class ConvexHullDynamic {
typedef long long coef_t;
typedef long long coord_t;
typedef long long val_t;
/*
* Line 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
* and 'xLeft' which is intersection with previous line in hull(first line has -INF)
*/
private:
struct Line {
coef_t a, b;
double xLeft;
enum Type {
line, maxQuery, minQuery
} type;
coord_t val;
explicit Line(coef_t aa = 0, coef_t bb = 0) : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {}
val_t valueAt(coord_t x) const { return a * x + b; }
friend bool areParallel(const Line &l1, const Line &l2) { return l1.a == l2.a; }
friend double intersectX(const Line &l1, const Line &l2) { return areParallel(l1, l2) ? INFINITY : 1.0 * (l2.b - l1.b) / (l1.a - l2.a); }
bool operator<(const Line &l2) const {
if(l2.type == line)
return this->a < l2.a;
if(l2.type == maxQuery)
return this->xLeft < l2.val;
if(l2.type == minQuery)
return this->xLeft > l2.val;
}
};
bool isMax; //whether or not saved envelope is top(search of max value)
public:
std::set< Line > hull; //envelope itself
private:
/*
* INFO: Check position in hull by iterator
* COMPLEXITY: O(1)
*/
bool hasPrev(std::set< Line >::iterator it) { return it != hull.begin(); }
bool hasNext(std::set< Line >::iterator it) { return it != hull.end() && std::next(it) != hull.end(); }
/*
* INFO: Check whether line l2 is irrelevant
* NOTE: Following positioning in hull must be true
* l1 is next left to l2
* l2 is right between l1 and l3
* l3 is next right to l2
* COMPLEXITY: O(1)
*/
bool irrelevant(const Line &l1, const Line &l2, const Line &l3) { return intersectX(l1, l3) <= intersectX(l1, l2); }
bool irrelevant(std::set< Line >::iterator it) {
return hasPrev(it) && hasNext(it)
&& (isMax && irrelevant(*std::prev(it), *it, *std::next(it))
|| !isMax && irrelevant(*std::next(it), *it, *std::prev(it)));
}
/*
* INFO: Updates 'xValue' of line pointed by iterator 'it'
* COMPLEXITY: O(1)
*/
std::set< Line >::iterator updateLeftBorder(std::set< Line >::iterator it) {
if(isMax && !hasPrev(it) || !isMax && !hasNext(it))
return it;
double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it));
Line buf(*it);
it = hull.erase(it);
buf.xLeft = val;
it = hull.insert(it, buf);
return it;
}
public:
explicit ConvexHullDynamic(bool isMax) : isMax(isMax) {}
/*
* INFO: Adding line to the envelope
* Line is of type 'y=a*x+b' represented by 2 coefficients 'a' and 'b'
* COMPLEXITY: Adding N lines(N calls of function) takes O(N*log N) time
*/
void addLine(coef_t a, coef_t b) {
//find the place where line will be inserted in set
Line l3 = Line(a, b);
auto it = hull.lower_bound(l3);
//if parallel line is already in set, one of them becomes irrelevant
if(it != hull.end() && areParallel(*it, l3)) {
if(isMax && it->b < b || !isMax && it->b > b)
it = hull.erase(it);
else
return;
}
//try to insert
it = hull.insert(it, l3);
if(irrelevant(it)) {
hull.erase(it);
return;
}
//remove lines which became irrelevant after inserting line
while(hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it));
while(hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it));
//refresh 'xLine'
it = updateLeftBorder(it);
if(hasPrev(it))
updateLeftBorder(std::prev(it));
if(hasNext(it))
updateLeftBorder(std::next(it));
}
val_t getBest(coord_t x) const {
Line q;
q.val = x;
q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery;
auto bestLine = hull.lower_bound(q);
if(isMax) --bestLine;
return bestLine->valueAt(x);
}
};
int main() {
int64 N, A[300000];
int64 X[300000], Y[300000];
scanf("%lld", &N);
for(int i = 0; i < N; i++) scanf("%lld", &A[i]);
for(int i = 0; i < N; i++) scanf("%lld", &X[i]);
for(int i = 0; i < N; i++) scanf("%lld", &Y[i]);
ConvexHullDynamic cht(false);
cht.addLine(X[0], X[0] * X[0] + Y[0] * Y[0]);
for(int i = 0; i < N; i++) {
int64 ret = cht.getBest(-2 * A[i]);
if(i + 1 == N) {
cout << ret + A[N - 1] * A[N - 1] << endl;
} else {
cht.addLine(X[i + 1], X[i + 1] * X[i + 1] + Y[i + 1] * Y[i + 1] + A[i] * A[i] + ret);
}
}
}