#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 100010;
void print(vector<ll> &a) {
for(int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
cout << endl;
}
int N, K, T;
int X[MN];
bool check(int x) {
//cout << "check : " << x << endl;
vector<ll> le, ri;
for(int i = 0; i < K; i++) {
ll d = 1LL * T * x - (X[i + 1] - X[i]);
le.push_back(d);
}
reverse(le.begin(), le.end());
for(int i = K; i < N - 1; i++) {
ll d = 1LL * T * x - (X[i + 1] - X[i]);
ri.push_back(d);
}
/*
print(le);
print(ri);
//*/
vector<ll> tmp;
ll sum = 0;
for(int i = 0; i < le.size(); i++) {
sum += le[i];
if(i == (int)le.size() - 1 || ((le[i] >= 0) ^ (le[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
}
le = tmp;
tmp.clear();
sum = 0;
for(int i = 0; i < ri.size(); i++) {
sum += ri[i];
if(i == (int)ri.size() - 1 || ((ri[i] >= 0) ^ (ri[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
}
ri = tmp;
/*
print(le);
print(ri);
//*/
vector<pair<ll, ll> > L, R;
ll init = 0;
if(le.size() && le[0] >= 0) init += le[0], le.erase(le.begin());
if(ri.size() && ri[0] >= 0) init += ri[0], ri.erase(ri.begin());
ll lim1 = 0;
ll lim2 = 0;
ll neg1 = 0;
ll neg2 = 0;
for(int i = (int)le.size() - 1; i >= 0; i--) {
if(le[i] >= 0) {
lim1 -= le[i];
lim1 = max(lim1, 0LL);
neg1 -= le[i];
}
else {
lim1 -= le[i];
neg1 -= le[i];
}
if(neg1 > 0) {
L.push_back({ lim1, neg1 });
lim1 = 0;
neg1 = 0;
}
}
for(int i = (int)ri.size() - 1; i >= 0; i--) {
if(ri[i] >= 0) {
lim2 -= ri[i];
lim2 = max(lim2, 0LL);
neg2 -= ri[i];
}
else {
lim2 -= ri[i];
neg2 -= ri[i];
}
if(neg2 > 0) {
R.push_back({ lim2, neg2 });
lim2 = 0;
neg2 = 0;
}
}
if(init < lim1 && init < lim2) return false;
if(init >= lim1 && init >= lim2) {
init -= neg1;
init -= neg2;
}
else if(init >= lim1) {
init -= neg1;
if(init < lim2) return false;
init -= neg2;
}
else {
init -= neg2;
if(init < lim1) return false;
init -= neg1;
}
//cout << init << endl;
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
/*
for(int i = 0; i < L.size(); i++) {
cout << "(" << L[i].first << ", " << L[i].second << ") ";
}
cout << endl;
for(int i = 0; i < R.size(); i++) {
cout << "(" << R[i].first << ", " << R[i].second << ") ";
}
cout << endl;
//*/
vector<ll> psum1(L.size());
vector<ll> psum2(R.size());
for(int i = 0; i < L.size(); i++) {
psum1[i] = L[i].second;
if(i) psum1[i] += psum1[i - 1];
}
for(int i = 0; i < R.size(); i++) {
psum2[i] = R[i].second;
if(i) psum2[i] += psum2[i - 1];
}
if(init < (psum1.size()? psum1.back() : 0) + (psum2.size()? psum2.back() : 0)) return false;
vector<int> pnt1(L.size());
vector<int> pnt2(R.size());
for(int i = 0; i < L.size(); i++) {
ll rem = i? init - psum1[i - 1] : init;
if(rem < L[i].first) return false;
rem -= L[i].first;
int s = 0, e = (int)psum2.size() - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(psum2[m] <= rem) {
p = m;
s = m + 1;
}
else e = m - 1;
}
pnt1[i] = p;
}
for(int i = 0; i < R.size(); i++) {
ll rem = i? init - psum2[i - 1] : init;
if(rem < R[i].first) return false;
rem -= R[i].first;
int s = 0, e = (int)psum1.size() - 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(psum1[m] <= rem) {
p = m;
s = m + 1;
}
else e = m - 1;
}
pnt2[i] = p;
}
int pos = (int)R.size() - 1;
int mn1 = 1e9;
int mn2 = 1e9;
for(int i = (int)L.size() - 1; i >= 0; i--) {
mn1 = min(mn1, pnt1[i]);
while(pos >= 0 && pos > mn1) {
mn2 = min(mn2, pnt2[pos]);
pos--;
}
if(mn2 < i) return false;
}
return true;
}
int main() {
scanf("%d %d %d", &N, &K, &T);
K--;
for(int i = 0; i < N; i++) {
scanf("%d", &X[i]);
}
int s = 0, e = 1e9 / T + 1, p = -1;
while(s <= e) {
int m = (s + e)>>1;
if(check(2 * m)) {
p = m;
e = m - 1;
}
else s = m + 1;
}
printf("%d", p);
}
Compilation message
sparklers.cpp: In function 'void print(std::vector<long long int>&)':
sparklers.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < le.size(); i++) {
~~^~~~~~~~~~~
sparklers.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ri.size(); i++) {
~~^~~~~~~~~~~
sparklers.cpp:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:147:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < R.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:157:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < L.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp:175:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < R.size(); i++) {
~~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:208:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &K, &T);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
3 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
3 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
3 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
256 KB |
Output is correct |
| 19 |
Correct |
2 ms |
256 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
