oj.uz

Submission #398078

# Submission time Handle Problem Language Result Execution time Memory
398078 2021-05-03T15:45:25 Z ntabc05101 Editor (BOI15_edi) C++14
15 / 100
 128 ms 34192 KB 
#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 - 1][j - 1]][j - 1];
               }
               
               cout << a[get_par(i, 0)] << "\n";
        }
        
        return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Integer -5 violates the range [0, 30]
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 34192 KB Output is correct
2 Correct 128 ms 34116 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 10088 KB Integer -23782 violates the range [0, 150000]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Integer -5 violates the range [0, 30]
2 Halted 0 ms 0 KB -