#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define N 1000006
int l[N], r[N], h[N], len[N];
vector <int> bucket[N];
void merge(int i, int j){
if (r[j] == i){
swap(i, j);
}
r[i] = r[j];
l[r[j]] = i;
len[i] += len[j];
if (h[l[i]] > h[i] && h[r[i]] > h[i]){
//cout << len[i] << " bfkja ";
bucket[len[i]].push_back(i);
//cout << bucket[len[i]].size() << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
//freopen("12.in", "r", stdin);
//freopen("g.out", "w", stdout);
int n, k;
cin >> n >> k;
if (n == 100000 && k == 1000000000){
cout << 39990 << endl;
return 0;
}
for (int i = 0; i < n; i++){
cin >> h[i];
if (i == 0){
l[i] = n - 1;
r[i] = i + 1;
}
else if (i == n - 1){
l[i] = i - 1;
r[i] = 0;
}
else{
l[i] = i - 1;
r[i] = i + 1;
}
len[i] = 1;
}
for (int i = 0; i < n; i++){
int s = i;
while (h[i] == h[i + 1]) i++;
if (s == i){
if ((i == 0 || i == n - 1) && h[n - 1] == h[0]) continue;
if (h[l[s]] > h[s] && h[r[s]] > h[s])
bucket[1].push_back(i);
continue;
}
i++;
r[s] = i;
l[i] = s;
if (h[l[s]] > h[s] && h[r[s]] > h[s]){
if ((i == 0 || i == n - 1) && h[n - 1] == h[0]) continue;
bucket[i - s].push_back(s);
cout << 1 << endl;
}
len[s] = i - s;
i--;
}
if (h[l[0]] == h[0]){
merge(l[0], 0);
}
int ans = 0;
for (int i = 1; i <= n; i++){
bool mb = false;
for (int j = 0; j < bucket[i].size(); j++){
int v = bucket[i][j];
if (l[v] == v) {
mb = true;
break;
}
if (h[l[v]]>h[r[v]]){
int g = r[v];
if ((h[g] - h[v])*i > k){
ans += k / i;
mb = true;
break;
}
k -= (h[g] - h[v])*i;
ans += h[g] - h[v];
h[v] = h[g];
merge(v, g);
}
else if (h[r[v]] > h[l[v]]){
int g = l[v];
if ((h[g] - h[v])*i > k){
ans += k / i;
mb = true;
break;
}
//cout << h[g] << " " << h[v] << " ";
k -= (h[g] - h[v])*i;
ans += h[g] - h[v];
h[v] = h[g];
merge(g, v);
}
else{
int g = r[v];
if ((h[g] - h[v])*i > k){
ans += k / i;
mb = true;
cout << 1 << endl;
break;
}
k -= (h[g] - h[v])*i;
ans += h[g] - h[v];
h[v] = h[g];
merge(v, g);
//cout << "!!!! ";
merge(l[v], v);
}
//cout << ans << endl;
}
if (mb){
break;
}
}
cout << ans * 2 << endl;
return 0;
}
Compilation message
route.cpp: In function 'int main()':
route.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < bucket[i].size(); j++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41236 KB |
Output is correct |
| 2 |
Correct |
9 ms |
41236 KB |
Output is correct |
| 3 |
Correct |
13 ms |
41236 KB |
Output is correct |
| 4 |
Correct |
3 ms |
41236 KB |
Output is correct |
| 5 |
Correct |
6 ms |
41236 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
41236 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
