Editorial for Bedao Regular Contest 07 - MTCAT


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Duyệt ngược các phần tử để cho vào mảng. Khi xét phần tử thứ ~i~, xóa hết các phần tử nhỏ hơn phần tử đang xét. Sau khi xóa hết các phần tử đó thì mảng sẽ là dãy những ngọn núi cao hơn đối với vị trí ~i~. Kết quả là phần tử có vị trí tương đương số bước nhảy, nếu số bước nhảy vượt quá kích cỡ thì in ~-1~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 +1;

int n;
int h[N], Jump[N], Result[N];
deque<int> q;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i=0; i<n; i++)
        cin >> h[i];
    for (int i=0; i<n; i++)
        cin >> Jump[i];
    for (int i=n-1; i>=0; i--){
        while (!q.empty() && h[i] >= h[q.back()])
            q.pop_back();
        int tmp = q.size() - Jump[i] + 1;
        if (tmp <= 0)
            Result[i] = -1;
        else 
            Result[i] = h[q[tmp - 1]];
        q.push_back(i);
    }
    for (int i=0; i<n; i++)
        cout << Result[i] << " ";
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.