Submission #828259

#	Time	Username	Problem	Language	Result	Execution time	Memory
828259		vjudge1	Editor (BOI15_edi)	C++14	100 / 100	228 ms	72456 KiB

edi

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

#define ll long long
#define vi vector<ll>
#define pi pair<ll,ll>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'

const int N = 1e6 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,a[N],lvl[N],up[N][LOG];
/*
    Edit state: lvl[i] =  0 
    Undo state: lvl[i] = -a[i]
    -> lift den cai active op gan nhat ma co lvl nho hon lvl[i]    
*/
ll lift(ll u,ll k){
    if(lvl[u] <= k) return u;
    for(ll i = LOG - 1;i >= 0;--i)
        if(lvl[up[u][i]] > k) u = up[u][i]; 
    return up[u][0];
}
void solve(){
    cin>>n;
    for(ll i = 1;i <= n;++i) cin>>a[i]; 
    for(ll i = 1;i <= n;++i){
        if(a[i] < 0){
            lvl[i] = -a[i];
            ll tmp = lift(i - 1,lvl[i] - 1);
            up[i][0] = lift(tmp-1,lvl[i] - 1); 
            for(ll j = 1;j < LOG;++j) up[i][j] = up[up[i][j-1]][j-1]; 
        }
        cout<<a[lift(i,0)]<<endl;
    }
}

signed main(){
    cin.tie(0); cout.tie(0); 
    ios_base::sync_with_stdio(false);
    ll t = 1; //cin>>t;
    while(t--) solve(); 
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

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