#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n, k; ll t;
scanf("%d %d %lld", &n, &k, &t);
vector<ll> X(n+1);
for(int i = 1; i <= n; ++i) {
scanf("%lld", &X[i]);
}
function<bool(ll)> possible = [&](ll s) {
auto x = X;
for(int i = 1; i <= n; ++i) {
x[i] -= 2LL * s * t * i;
}
x[0] = LLONG_MAX;
x.push_back(LLONG_MIN);
vi pg(n+1), ns(n+1), ng(n+1), ps(n+1);
vector<ll> pg_min = x, ns_max = x;
vector<ll> ng_min = x, ps_max = x;
vector<int> stk = {0};
for(int i = 1; i <= n; ++i) {
while(x[stk.back()] < x[i]) {
pg_min[i] = min(pg_min[i], pg_min[stk.back()]);
stk.pop_back();
}
pg[i] = stk.back();
stk.push_back(i);
}
stk.clear();
stk = {n+1};
for(int i = n; i >= 1; --i) {
while(x[stk.back()] > x[i]) {
ns_max[i] = max(ns_max[i], ns_max[stk.back()]);
stk.pop_back();
}
ns[i] = stk.back();
stk.push_back(i);
}
stk.clear();
x[0] = LLONG_MIN, x[n+1] = LLONG_MAX;
stk = {0};
for(int i = 1; i <= n; ++i) {
while(x[stk.back()] >= x[i]) {
ps_max[i] = max(ps_max[i], ps_max[stk.back()]);
stk.pop_back();
}
ps[i] = stk.back();
stk.push_back(i);
}
stk.clear();
stk = {n+1};
for(int i = n; i >= 1; --i) {
while(x[stk.back()] <= x[i]) {
ng_min[i] = min(ng_min[i], ng_min[stk.back()]);
stk.pop_back();
}
ng[i] = stk.back();
stk.push_back(i);
}
int l1 = k, r1 = k;
while(pg[l1] >= 1 or ns[r1] <= n) {
if(pg[l1] >= 1 and pg_min[l1] >= x[r1])
l1 = pg[l1];
else if(ns[r1] <= n and ns_max[r1] <= x[l1])
r1 = ns[r1];
else
return false;
}
int l2 = 1, r2 = n;
while(ng[l2] <= k or ps[r2] >= k) {
if(ng[l2] <= k and ng_min[l2] >= x[r2])
l2 = ng[l2];
else if(ps[r2] >= k and ps_max[r2] <= x[l2])
r2 = ps[r2];
else
return false;
}
return l1 == l2 and r1 == r2;
};
int lo = 1, hi = 1e5, opt = -1;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(possible(mid)) {
opt = mid;
hi = mid-1;
} else {
lo = mid+1;
}
}
printf("%d\n", opt);
return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/
Compilation message
sparklers.cpp: In function 'int main(int, const char**)':
sparklers.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d %d %lld", &n, &k, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | scanf("%lld", &X[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
