# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
876573 | rukashii | Split the sequence (APIO14_sequence) | C++17 | 880 ms | 84468 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;
using ll = long long;
ll pref[100100];
struct line {
ll m, c;
int idx;
};
struct CHT {
deque<line> dq;
int p;
void clear() {
while (!dq.empty()) dq.pop_back();
p = 0;
}
bool replace(line x, line y, line z) {
return (x.c - y.c) * (z.m - x.m) >= (x.c - z.c) * (y.m - x.m);
}
void add(line x) {
while (dq.size() > 1 && replace(dq[dq.size() - 2], dq.back(), x)) {
dq.pop_back();
}
dq.push_back(x);
}
line query(ll x) {
p = min(p, (int)dq.size() - 1);
while (p < (int)dq.size() - 1 && dq[p].c - dq[p + 1].c < x * (dq[p + 1].m - dq[p].m)) p++;
return dq[p];
}
} cht;
# | 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... |