제출 #1346363

#제출 시각아이디문제언어결과실행 시간메모리
1346363SzymonKrzywdaEditor (BOI15_edi)C++20
100 / 100
98 ms27044 KiB
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;
const int MAXN = 3e5 + 7;

#define ff first 
#define ss second 

const int LOG = 19;
int jump[MAXN][LOG];
int ranks[MAXN];
int tab[MAXN];

int find(int v, int r2) {
    if (ranks[v] <= r2) return v;
    for (int k = LOG - 1; k >= 0; k--) {
        if (ranks[jump[v][k]] > r2) v = jump[v][k];
    }
    return jump[v][0];
}

int main() {
    ios_base::sync_with_stdio(0);   
    cin.tie(0);
    int n, val;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tab[i];
        ranks[i] = max(-tab[i], 0);
        if (ranks[i] == 0) {
            cout << tab[i] << '\n';
            continue;
        }

        int v2 = find(i - 1, ranks[i] - 1);
        jump[i][0] = find(v2 - 1, ranks[i] - 1);
        for (int k = 1; k < LOG; k++) jump[i][k] = jump[jump[i][k - 1]][k - 1];
        cout << tab[find(i, 0)] << '\n';
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...