# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95842 | diamond_duke | Sparklers (JOI17_sparklers) | C++11 | 400 ms | 16892 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 <functional>
#include <cstdio>
using ll = long long;
struct ST_table
{
std::function<int (int, int)> comp;
int emp, lg[100005], arr[25][100005];
template <typename T> ST_table(int n, int _emp, T _comp) : comp(_comp), emp(_emp)
{
lg[0] = lg[1] = 0;
for (int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
for (int i = 0; i < n; i++)
arr[0][i] = i;
for (int i = 1; i <= lg[n]; i++)
{
for (int j = 0; j + (1 << i) <= n; j++)
arr[i][j] = comp(arr[i - 1][j], arr[i - 1][j + (1 << i - 1)]);
}
}
inline int operator ()(int l, int r)
{
if (l > r)
return emp;
int len = lg[r - l + 1];
return comp(arr[len][l], arr[len][r - (1 << len) + 1]);
}
};
ll val[100005];
int arr[100005], st[100005], pre[100005], nxt[100005];
inline bool check(int n, int stp, ll lim)
{
for (int i = 0; i < n; i++)
val[i] = arr[i] - lim * i;
val[n] = 1e18;
val[n + 1] = -1e18;
ST_table qmin(n, n, [&] (int x, int y) { return val[x] < val[y] ? x : y; });
ST_table qmax(n, n + 1, [&] (int x, int y) { return val[x] > val[y] ? x : y; });
int tp = 0;
st[tp] = -1;
for (int i = 0; i < n; i++)
{
while (tp && val[st[tp]] <= val[i])
tp--;
pre[i] = st[tp];
st[++tp] = i;
}
tp = 0;
st[tp] = n;
for (int i = n - 1; i >= 0; i--)
{
while (tp && val[st[tp]] >= val[i])
tp--;
nxt[i] = st[tp];
st[++tp] = i;
}
int l = stp, r = stp;
while (l || r != n - 1)
{
int x = pre[l], y = nxt[r];
if (~x && val[qmin(x + 1, l - 1)] >= val[r])
l = x;
else if (y != n && val[qmax(r + 1, y - 1)] <= val[l])
r = y;
else
{
if (!l)
return val[qmax(r + 1, n - 1)] <= val[l];
if (r == n - 1)
return val[qmin(0, l - 1)] >= val[r];
x = qmin(0, l - 1);
y = qmax(r + 1, n - 1);
if (val[x] < val[r] || val[y] > val[l])
return false;
int a = qmax(0, x), b = qmin(y, n - 1);
if (val[a] >= val[y])
l = a;
else if (val[b] <= val[x])
r = b;
else
return false;
}
}
return true;
}
int main()
{
// freopen("loj-2392.in", "r", stdin);
int n, stp, T;
scanf("%d%d%d", &n, &stp, &T);
for (int i = 0; i < n; i++)
scanf("%d", arr + i);
int l = 0, r = (arr[n - 1] - arr[0]) / T / 2 + 1, res = -1;
while (l <= r)
{
int m = l + r >> 1;
if (check(n, stp - 1, (ll)2 * m * T))
{
res = m;
r = m - 1;
}
else
l = m + 1;
}
printf("%d\n", res);
return 0;
}
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... |