結果
問題 | No.703 ゴミ拾い Easy |
ユーザー | ei1333333 |
提出日時 | 2018-06-15 22:53:12 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 140 ms / 1,500 ms |
コード長 | 4,675 bytes |
コンパイル時間 | 2,270 ms |
コンパイル使用メモリ | 206,068 KB |
実行使用メモリ | 10,748 KB |
最終ジャッジ日時 | 2023-08-30 18:56:26 |
合計ジャッジ時間 | 7,573 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,504 KB |
testcase_01 | AC | 3 ms
7,596 KB |
testcase_02 | AC | 2 ms
7,480 KB |
testcase_03 | AC | 2 ms
7,568 KB |
testcase_04 | AC | 2 ms
7,576 KB |
testcase_05 | AC | 2 ms
7,800 KB |
testcase_06 | AC | 2 ms
7,580 KB |
testcase_07 | AC | 2 ms
7,500 KB |
testcase_08 | AC | 3 ms
7,536 KB |
testcase_09 | AC | 2 ms
7,528 KB |
testcase_10 | AC | 3 ms
7,580 KB |
testcase_11 | AC | 2 ms
7,672 KB |
testcase_12 | AC | 3 ms
7,576 KB |
testcase_13 | AC | 3 ms
7,548 KB |
testcase_14 | AC | 3 ms
7,816 KB |
testcase_15 | AC | 3 ms
7,508 KB |
testcase_16 | AC | 3 ms
7,548 KB |
testcase_17 | AC | 3 ms
7,544 KB |
testcase_18 | AC | 3 ms
7,536 KB |
testcase_19 | AC | 3 ms
7,504 KB |
testcase_20 | AC | 3 ms
7,572 KB |
testcase_21 | AC | 3 ms
7,552 KB |
testcase_22 | AC | 3 ms
7,660 KB |
testcase_23 | AC | 3 ms
7,556 KB |
testcase_24 | AC | 138 ms
10,464 KB |
testcase_25 | AC | 138 ms
10,748 KB |
testcase_26 | AC | 138 ms
10,464 KB |
testcase_27 | AC | 138 ms
10,544 KB |
testcase_28 | AC | 138 ms
10,488 KB |
testcase_29 | AC | 139 ms
10,496 KB |
testcase_30 | AC | 140 ms
10,568 KB |
testcase_31 | AC | 138 ms
10,580 KB |
testcase_32 | AC | 138 ms
10,496 KB |
testcase_33 | AC | 139 ms
10,456 KB |
testcase_34 | AC | 87 ms
10,624 KB |
testcase_35 | AC | 87 ms
10,524 KB |
testcase_36 | AC | 88 ms
10,720 KB |
testcase_37 | AC | 87 ms
10,732 KB |
testcase_38 | AC | 87 ms
10,568 KB |
testcase_39 | AC | 87 ms
10,552 KB |
testcase_40 | AC | 87 ms
10,488 KB |
testcase_41 | AC | 87 ms
10,504 KB |
testcase_42 | AC | 87 ms
10,448 KB |
testcase_43 | AC | 88 ms
10,488 KB |
testcase_44 | AC | 2 ms
7,524 KB |
testcase_45 | AC | 2 ms
7,608 KB |
testcase_46 | AC | 102 ms
10,452 KB |
testcase_47 | AC | 100 ms
10,448 KB |
testcase_48 | AC | 3 ms
7,724 KB |
testcase_49 | AC | 4 ms
7,540 KB |
コンパイルメッセージ
main.cpp: メンバ関数 ‘bool ConvexHullDynamic::Line::operator<(const ConvexHullDynamic::Line&) const’ 内: main.cpp:42:5: 警告: 制御が非 void 関数の終りに到達しました [-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); } } }