Submission #300776

#TimeUsernameProblemLanguageResultExecution timeMemory
300776kaplanbarZalmoxis (BOI18_zalmoxis)C++14
30 / 100
672 ms18248 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int N = 1e6 + 5; struct Element { int x, l, r; bool operator<(Element other) const { if(x == other.x) { return l > other.l; } return x > other.x; } }; int n, k, a[N]; priority_queue<Element> q; int main() { ios_base::sync_with_stdio(false); cin >> n >> k; assert(k == 1); for(int i = 0; i < n; i++) { cin >> a[i]; q.push((Element){a[i], i, i}); } pair<int,int> Ans; while(1) { if(q.size() == 1) { assert(q.top().x == -30); break; } int mn = q.top().x; pair<int,int> le = make_pair(q.top().l, q.top().r); q.pop(); if(mn == q.top().x && le.second == q.top().l - 1) { auto val = (Element){mn + 1, le.first, q.top().r}; q.pop(); q.push(val); } else { // Once we find the answer, we can stop searching // since it is guaranteed to have answer. Ans = make_pair(mn, le.second + 1); break; } } for(int i = 0; i < n + k; i++) { if(Ans.second == i) { cout << Ans.first << " "; } if(i < n) cout << a[i] << " "; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...