#include <bits/stdc++.h>
using namespace std;
const int lim = 1e9, Nmax = 1e5 + 5;
typedef long long ll;
const ll Target = 1e16;
int n, K, T;
int X[Nmax];
struct Pair
{
mutable ll first, second;
bool operator < (const Pair &other) const
{
if(first == other.first) return second < other.second;
return first < other.first;
}
};
void add(vector<Pair> &w, ll A, ll B)
{
while(w.size())
{
if(B >= w.back().first)
B += w.back().second - w.back().first;
else if(A > B)
{
A += w.back().first - B;
B = w.back().second;
}
else break;
w.pop_back();
}
// assert(A <= B);
// if(w.size()) assert(w.back().first >= B);
w.push_back({A, B});
}
ll transformm(vector<int> &v, vector<Pair> &w)
{
int i = 0;
ll sum = 0, K, Q;
while(i<v.size() && v[i] > 0) sum += v[i++];
add(w, 0, Target);
vector<Pair> to_add;
for(; i<v.size(); )
{
K = 0;
while(i < v.size() && v[i] <= 0) K += v[i++];
Q = 0;
while(i < v.size() && v[i] > 0) Q += v[i++];
to_add.push_back({-K, Q});
}
reverse(to_add.begin(), to_add.end());
for(auto it : to_add)
add(w, it.first, it.second);
reverse(w.begin(), w.end());
return sum;
}
void Merge(vector<Pair> &a, vector<Pair> &b, vector<Pair> &c)
{
multiset<Pair> S;
a.back().second -= Target;
b.back().second -= Target;
Pair A = a.back(), B = b.back();
a.pop_back(); b.pop_back();
assert(A.second >= 0);
assert(B.second >= 0);
for(auto it : b) S.insert(it);
bool ok1 = 1, ok2 = 1;
if(A.first <= A.second) a.push_back(A), ok1 = 0;
if(B.first <= B.second) b.push_back(B), ok2 = 0;
for(auto it : a)
{
multiset<Pair> :: iterator t;
t = S.insert(it);
while(t != S.begin() && prev(t)->second > t->first)
{
t->second += prev(t)->second - t->first;
t->first = prev(t)->first;
S.erase(prev(t));
}
while(next(t) != S.end() && t->second > next(t)->first)
{
t->second += next(t)->second - next(t)->first;
S.erase(next(t));
}
}
for(auto it : S) c.push_back(it);
if(ok1 && ok2)
{
c.push_back(A);
c.push_back(B);
ll v1, v2;
v1 = A.first + max(0LL, B.first - A.second);
v2 = B.first + max(0LL, A.first - B.second);
if(v1 > v2) swap(c[c.size()-2], c.back());
}
else if(ok1) c.push_back(A);
else if(ok2) c.push_back(B);
}
bool check(int S)
{
if(2LL * S * T >= lim) return 1;
vector<int> A, B;
int i;
for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
for(i=K+1; i<=n; ++i) B.push_back(2 * S * T - (X[i] - X[i-1]));
vector<Pair> a, b, c;
ll sum = 0;
sum = transformm(A, a) + transformm(B, b);
Merge(a, b, c);
for(auto it : c)
{
if(sum < it.first) return 0;
sum -= it.first;
sum += it.second;
}
return 1;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
int i;
cin >> n >> K >> T;
for(i=1; i<=n; ++i) cin >> X[i];
int st = 0, dr = 1e9, mid;
while(st <= dr)
{
mid = (st+dr) / 2;
if(check(mid)) dr = mid-1;
else st = mid+1;
}
cout << st << '\n';
return 0;
}
Compilation message
sparklers.cpp: In function 'll transformm(std::vector<int>&, std::vector<Pair>&)':
sparklers.cpp:47:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<v.size() && v[i] > 0) sum += v[i++];
~^~~~~~~~~
sparklers.cpp:52:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; i<v.size(); )
~^~~~~~~~~
sparklers.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < v.size() && v[i] <= 0) K += v[i++];
~~^~~~~~~~~~
sparklers.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < v.size() && v[i] > 0) Q += v[i++];
~~^~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:130:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
^~~
sparklers.cpp:130:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
1 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
1 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
404 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
1 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
1 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
404 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
1 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
1 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
1 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
404 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
