# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70878 | aquablitz11 | Aliens (IOI16_aliens) | C++14 | 198 ms | 9284 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>
#include "aliens.h"
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
using pii = pair<int, int>;
#define F first
#define S second
struct CHT {
struct line {
ll m, c;
int cnt;
line(ll m, ll c, int cnt) : m(m), c(c), cnt(cnt) {}
ll get(ll x) { return m*x + c; }
};
bool bad(line l1, line l2, line l3) {
return (l3.c-l1.c)*(l1.m-l2.m) <= (l2.c-l1.c)*(l1.m-l3.m);
}
vector<line> f;
int idx;
void update(ll m, ll c, int cnt) {
line l(m, c, cnt);
while (f.size() > 1 && bad(f[f.size()-2], f[f.size()-1], l))
f.pop_back();
f.push_back(l);
}
pli query(ll x) {
idx = min(idx, (int)f.size()-1);
Compilation message (stderr)
# | 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... |