Submission #706476

#	Time	Username	Problem	Language	Result	Execution time	Memory
706476		alvingogo	Editor (BOI15_edi)	C++14	100 / 100	159 ms	33688 KiB

edi

#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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37