oj.uz

Submission #706476

# Submission time Handle Problem Language Result Execution time Memory
706476 2023-03-06T16:53:35 Z alvingogo Editor (BOI15_edi) C++14
100 / 100
 159 ms 33688 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int main(){
    AquA;
    int n;
    cin >> n;
    vector<vector<int> > as(21,vector<int>(n));
    vector<int> lv,az;
    auto get=[&](int x,int a){
        if(x<0){
            return -1;
        }
        if(lv[x]<a){
            return x;
        }
        for(int j=20;j>=0;j--){
            if(lv[as[j][x]]>=a){
                x=as[j][x];
            }
        }
        x=as[0][x];
        return x;  
    };
    int ans=0;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        if(a<0){
            a=-a;
            lv.push_back(a);
            int x=get(i-1,a);
            //cout << x << endl;
            int y=get(x-1,a);
            if(y>=0){
                as[0][i]=y;
                ans=az[as[20][y]];
            }
            else{
                as[0][i]=i;
                ans=0;
            }
        }
        else{
            lv.push_back(0);
            as[0][i]=i;
            ans=a;
        }
        az.push_back(ans);
        cout << ans << "\n";
        for(int j=1;j<21;j++){
            as[j][i]=as[j-1][as[j-1][i]];
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 32044 KB Output is correct
2 Correct 129 ms 32952 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15920 KB Output is correct
2 Correct 73 ms 19208 KB Output is correct
3 Correct 125 ms 25360 KB Output is correct
4 Correct 134 ms 32872 KB Output is correct
5 Correct 128 ms 33632 KB Output is correct
6 Correct 119 ms 30872 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 796 KB Output is correct
10 Correct 140 ms 32044 KB Output is correct
11 Correct 129 ms 32952 KB Output is correct
12 Correct 70 ms 15920 KB Output is correct
13 Correct 73 ms 19208 KB Output is correct
14 Correct 125 ms 25360 KB Output is correct
15 Correct 134 ms 32872 KB Output is correct
16 Correct 128 ms 33632 KB Output is correct
17 Correct 119 ms 30872 KB Output is correct
18 Correct 138 ms 33496 KB Output is correct
19 Correct 122 ms 33504 KB Output is correct
20 Correct 159 ms 32116 KB Output is correct
21 Correct 130 ms 32972 KB Output is correct
22 Correct 122 ms 33688 KB Output is correct