Help in understanding my mistake for problem https://mirror.codeforces.com/contest/1313/problem/C1

Revision en1, by vaibhav_dsa, 2024-06-25 07:37:14

https://mirror.codeforces.com/contest/1313/submission/267250753

# include<bits/stdc++.h>

using namespace std;

# define ll long long

void recursive(vector& arr, set<pair<ll,ll>>& st, ll left_index, ll right_index, vector& suffix) { if (left_index >= right_index || st.empty()) { return; }

auto it = st.begin();
ll index = it->second;
ll min_value = it->first;

if (index == left_index) {
left_index++;
st.erase(it);
recursive(arr, st, left_index, right_index, suffix);
} else if (index == right_index) {
right_index--;
st.erase(it);
recursive(arr, st, left_index, right_index, suffix);
} else {
if (suffix[index - 1] - (suffix[left_index] - arr[left_index]) < suffix[right_index] - suffix[index]) {
for (int i = index; i >= left_index; i--) {
st.erase({arr[i], i});
arr[i] = min_value;
}
left_index = index + 1;
} else {
for (int i = index; i <= right_index; i++) {
st.erase({arr[i], i});
arr[i] = min_value;
}
right_index = index - 1;
}
recursive(arr, st, left_index, right_index, suffix);
}

}

void solve() { int n; cin >> n;

vector<ll> arr(n);
vector<ll> suffix(n);
set<pair<ll,ll>> st;
ll prev = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
suffix[i] = prev + arr[i];
prev = suffix[i];
st.insert({arr[i], i});
}

recursive(arr, st, 0, n - 1, suffix);

for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;

}

int main() { solve(); return 0; }

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 vaibhav_dsa 2024-06-25 07:37:14 1897 Initial revision (published)