# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
406332 | drogskol | Aliens (IOI16_aliens) | C++17 | 1 ms | 204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
//base:[Convex-Hull Trick - sataniC++](http://s...content-available-to-author-only...g.com/entry/2016/08/16/181331#fn-534591c8)
//追加する直線の傾きは単調(最小値なら傾きは単調減少、最大値なら傾きは単調増加)
template<typename T>
struct ConvecHullTrick {
typedef pair<T,T> Line;
vector<Line> lines; //直線(傾き,切片)
bool isMonotonicX; //最小値(最大値)を求めるxが単調であるか
function<bool(T l, T r)> comp; //最小/最大を判断する関数
int head=0;
//flag:クエリは単調? compFunc:求めるのは最大値?
ConvecHullTrick(bool flagX=0,bool compFunc=0):isMonotonicX(flagX){
if(compFunc)comp=[](T l,T r){return l<=r;};
else comp=[](T l,T r){return l>=r;};
};
//直線l1,l2,l3のうちl2が不必要であるかどうか
bool check(Line l1,Line l2,Line l3){
if(l1<l3)swap(l1,l3);
T a1=l1.first,a2=l2.first,a3=l3.first,b1=l1.second,b2=l2.second,b3=l3.second;
return (b3-b2)*(a2-a1)>=(b2-b1)*(a3-a2);
}
//直線y=ax+bを追加する 単調性から付け足すのは一番後ろで、不必要なやつが消えるまで一番後ろを消したら付け足す
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |