제출 #398080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398080		ntabc05101	Editor (BOI15_edi)	C++14	100 / 100	218 ms	34884 KiB

edi

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

const int mxN = 300000;
const int lgN = 19;

int a[mxN + 5], w[mxN + 5], par[mxN + 5][lgN + 5];

int get_par(int u, int mx_w) {
        if (w[u] <= mx_w) return u;
        for (int i = lgN - 1; i >= 0; i--) {
                if (w[par[u][i]] > mx_w) {
                        u = par[u][i];
                }
        }
        return par[u][0];
}

int main() {
        cin.tie(0)->sync_with_stdio(0);
        
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
               cin >> a[i];
               if (a[i] < 0) {
                       w[i] = -a[i];
                       int b = get_par(i - 1, w[i] - 1);
                       par[i][0] = get_par(b - 1, w[i] - 1);
                      
                       for (int j = 1; j < lgN; j++) par[i][j] = par[par[i][j - 1]][j - 1];
               }
               
               cout << a[get_par(i, 0)] << "\n";
        }
        
        return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37