#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
int const nmax = 100000;
int const inf = 1000000000;
int v[5 + nmax];
ll arr[2][5 + nmax];
ll prefmin[5 + nmax], suffmin[5 + nmax];
ll prefmax[5 + nmax], suffmax[5 + nmax];
bool solve(int n, int k, int t, int speed) {
ll base = speed * t * 2LL;
int ptr = 0, ptr2 = 0;
arr[0][++ptr] = 0;
arr[1][++ptr2] = 0;
for(int i = k - 1; 1 <= i; i--) {
arr[0][++ptr] = -(v[i + 1] - v[i]);
arr[0][++ptr] = base;
}
for(int i = k + 1; i <= n; i++) {
arr[1][++ptr2] = -(v[i] - v[i - 1]);
arr[1][++ptr2] = base;
}
for(int i = 1; i <= ptr; i++)
arr[0][i] += arr[0][i - 1];
for(int i = 1; i <= ptr2; i++)
arr[1][i] += arr[1][i - 1];
/*
std::cout << "Visual Map:\n";
for(int i = 1; i <= ptr; i++) {
for(int j = 1; j <= ptr2; j++)
std::cout << (0 <= (base + arr[0][i] + arr[1][j]));
std::cout << '\n';
}
*/
int smax = 1;
for(int i = 1;i <= ptr; i++)
if(arr[0][smax] < arr[0][i])
smax = i;
std::vector<int> stLeft, stRight;
stLeft.push_back(1);
for(int i = 2; i <= smax; i++)
if(arr[0][stLeft.back()] <= arr[0][i])
stLeft.push_back(i);
stRight.push_back(ptr);
for(int i = ptr - 1; smax <= i; i--)
if(arr[0][stRight.back()] <= arr[0][i])
stRight.push_back(i);
for(int i = 1; i <= ptr2; i++) {
suffmin[i] = prefmin[i] = arr[1][i];
suffmax[i] = prefmax[i] = arr[1][i];
}
for(int i = 2;i <= ptr2; i++) {
prefmin[i] = std::min(prefmin[i], prefmin[i - 1]);
prefmax[i] = std::max(prefmax[i], prefmax[i - 1]);
}
for(int i = ptr2 - 1; 1 <= i; i--) {
suffmin[i] = std::min(suffmin[i], suffmin[i + 1]);
suffmax[i] = std::max(suffmax[i], suffmax[i + 1]);
}
if(prefmin[ptr2] + arr[0][smax] + base < 0)
return 0;
auto findPointUpper = [&](int id) {
int x = 0;
for(int jump = (1 << 20); 0 < jump; jump /= 2)
if(x + jump <= ptr2 && 0 <= prefmin[x + jump] + arr[0][id] + base)
x += jump;
return x;
};
auto findPointLower = [&](int id) {
int x = ptr2 + 1;
for(int jump = (1 << 20); 0 < jump; jump /= 2)
if(1 <= x - jump && 0 <= suffmin[x - jump] + arr[0][id] + base)
x -= jump;
return x;
};
auto rangeMin = [&](int x, int y) {
ll valmin = arr[0][x];
for(int i = x;i <= y; i++)
valmin = std::min(valmin, arr[0][i]);
return valmin;
};
for(int i = 1; i < stLeft.size(); i++) {
int lim = findPointUpper(stLeft[i - 1]);
if(lim < 1)
return 0;
if(rangeMin(stLeft[i - 1], stLeft[i]) + base + prefmax[lim] < 0)
return 0;
}
for(int i = 1; i < stRight.size(); i++) {
int lim = findPointLower(stRight[i - 1]);
if(n < lim)
return 0;
if(rangeMin(stRight[i], stRight[i - 1]) + base + suffmax[lim] < 0)
return 0;
}
return 1;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n, k, t;
std::cin >> n >> k >> t;
for(int i = 1; i <= n; i++)
std::cin >> v[i];
int speed = 0;
for(int jump = (1 << 30); 0 < jump; jump /= 2)
if((speed + jump) <= inf / t && solve(n, k, t, speed + jump) == 0)
speed += jump;
std::cout << speed + 1 << '\n';
return 0;
}
Compilation message
sparklers.cpp: In function 'bool solve(int, int, int, int)':
sparklers.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 1; i < stLeft.size(); i++) {
| ~~^~~~~~~~~~~~~~~
sparklers.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int i = 1; i < stRight.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
440 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
440 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
440 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
