oj.uz

Submission #301015

# Submission time Handle Problem Language Result Execution time Memory
301015 2020-09-17T15:52:53 Z kaplanbar Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 888 ms 19660 KB 
#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;
    }
};
struct Ans {
    int x, l, t;
    bool operator<(Ans other) const {
        if(l == other.l) {
            return t < other.t;
        }
        return l < other.l;
    }
};
int n, k;
priority_queue<Element> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        q.push((Element){a[i], i, i});
    }
    int total = k;
    vector<Ans> ans;
    int tim = 0;
    while(1) {
        if(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 {
            ans.push_back((Ans){mn, le.second + 1, tim++});
            total--;
            q.push((Element){mn + 1, le.first, le.second});
        }
    }
    sort(ans.begin(), ans.end());
    int ptr = 0;
    for(int i = 0; i <= n; i++) {
        if(ptr < (int)ans.size()) {
            int end = ptr;
            // Reverse the stack to process in correct order
            while(end < (int)ans.size() && ans[end].l == i) {
                end++;
            }
            stack<int> s;
            for(int j = end - 1; j >= ptr; j--) {
                s.push(ans[j].x);
            }
            ptr = end;
            while(s.size()) {
                while(total > 0 && s.top() > 0) {
                    total--;
                    int x  = s.top();
                    s.pop();
                    s.push(x - 1);
                    s.push(x - 1);
                }
                cout << s.top() << " ";
                s.pop();
            }
        }
        if(i != n) cout << a[i] << " ";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 820 ms 18236 KB Output is correct
2 Correct 826 ms 18240 KB Output is correct
3 Correct 831 ms 18256 KB Output is correct
4 Correct 824 ms 18232 KB Output is correct
5 Correct 853 ms 18252 KB Output is correct
6 Correct 827 ms 18240 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 18256 KB Output is correct
2 Correct 757 ms 18252 KB Output is correct
3 Correct 762 ms 18252 KB Output is correct
4 Correct 888 ms 18240 KB Output is correct
5 Correct 822 ms 18256 KB Output is correct
6 Correct 840 ms 18380 KB Output is correct
7 Correct 839 ms 18252 KB Output is correct
8 Correct 857 ms 18236 KB Output is correct
9 Correct 782 ms 19660 KB Output is correct
10 Correct 352 ms 12000 KB Output is correct
11 Correct 529 ms 15196 KB Output is correct
12 Correct 91 ms 2296 KB Output is correct
13 Correct 108 ms 2320 KB Output is correct
14 Correct 96 ms 2428 KB Output is correct