# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
138511 | mosesmayer | Aliens (IOI16_aliens) | C++17 | 2024 ms | 8272 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 "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
struct Line{
LL m, c;
Line(LL m = 0, LL c = 0): m(m), c(c){}
LL get(LL x){return m * x + c;}
};
struct ConvexHull{
int sz, B;
Line *hull;
ConvexHull(int n): sz(0), B(0){
hull = new Line[++n];
}
bool is_bad(int curr, int prev, int next){
Line c = hull[curr], p = hull[prev], n = hull[next];
return (c.c - n.c) * (c.m - p.m) <= (p.c - c.c) * (n.m - c.m);
}
void add_line(LL m, LL c){
hull[sz++] = Line(m, c);
while (sz > 2 && is_bad(sz-2, sz-3, sz-1)){
hull[sz-2] = hull[sz-1]; sz--;
}
B = min(B, sz - 1);
# | 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... |