vaibhav_dsa's blog

By vaibhav_dsa, history, 3 weeks ago, In English

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; }

  • Vote: I like it
  • -14
  • Vote: I do not like it