Submission #446466

#	Time	Username	Problem	Language	Result	Execution time	Memory
446466		SirCovidThe19th	Editor (BOI15_edi)	C++14	100 / 100	754 ms	50324 KiB

edi

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

const int mx = 3e5+5;

int n, ans[mx], up[mx][19], mn[mx][19]; 

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        int a; cin >> a; if (a > 0){ ans[i] = a; continue; }
        a *= -1; int pos = i-1;
        for (int l = 18; l >= 0; l--) if (mn[pos][l] >= a) pos = up[pos][l];
        up[i][0] = pos-1, mn[i][0] = a, ans[i] = ans[pos-1];
        for (int l = 1; l < 18; l++){
            up[i][l] = up[up[i][l-1]][l-1];
            mn[i][l] = min(mn[i][l-1], mn[up[i][l-1]][l-1]);
        }
    }for (int i = 1; i <= n; i++) cout<<ans[i]<<endl;
}

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