oj.uz

Submission #113240

# Submission time Handle Problem Language Result Execution time Memory
113240 2019-05-24T11:53:28 Z Abelyan Editor (BOI15_edi) C++17
100 / 100
 1147 ms 270588 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v),v.end()))
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x);
#define dbgv(v);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
#ifdef ALEXPC
#define dbg(x); cout<<#x<<" = "<<x<<endl
#define dbgv(v); cout<<#v<<" = ["; trav(tv,v)cout<<"tv,";cout<<"]"<<endl
#endif

//const int N=100,M=N*N;
const ll MOD=1000*1000*1000+7;

const int N=2*1e6+6,M=6*N,MAXND=N;
const ll MX=1000000000ll*1000000000ll;

typedef struct item * pitem;



struct item{
    int key,val,mx;
    pitem l,r;
    item(pitem _l,pitem _r,int _key,int _val,int _mx){
        l=_l;
        r=_r;
        key=_key;
        val=_val;
        mx=_mx;
    }
    int get_mx(pitem v){
        if (!v)return 0;
        return v->mx;
    }
    pitem push(int nkey,int nval){
        pitem _l=l,_r=r;
        int _val=val;
        if (nkey<key){
            _l=l->push(nkey,nval);
        }
        else if (nkey==key){
            _val=nval;
        }
        else{
            _r=r->push(nkey,nval);
        }
        return new item(_l,_r,key,_val,max(max(get_mx(_l),get_mx(_r)),_val));
    }
    int get(int nkey){
        //cout<<key<<endl;
        if (nkey<key){
            return l->get(nkey);
        }
        else if (nkey==key){
            return max(get_mx(l),val);
        }
        else {
            return max(val,max(get_mx(l),r->get(nkey)));
        }
    }
};

pitem make(int tl,int tr){
    if (tl>tr)return NULL;
    int tm=(tl+tr)/2;
    return new item(make(tl,tm-1),make(tm+1,tr),tm,0,0);
}

pitem ver[N];
int pat[N];


int main(){
    fastio;
    srng;
    int n;
    cin>>n;
    ver[0]=make(0,n);
    FORT(i,1,n){
        int tv;
        cin>>tv;
        if (tv>0){
            ver[i]=ver[i-1]->push(0,i);
            pat[i]=tv;
        }
        else{
            tv=-tv;
            int kpnel=ver[i-1]->get(tv-1)-1;
            //cout<<1<<endl;
            pat[i]=pat[kpnel];
            ver[i]=ver[kpnel]->push(tv,i);
        }
        cout<<pat[i]<<endl;
    }
    return 0;
}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
2 1 2
2 2 5
2 3 4
2 3 2
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 14 ms 3456 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 14 ms 3384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 15 ms 3456 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 16 ms 3456 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 267896 KB Output is correct
2 Correct 868 ms 268000 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 128276 KB Output is correct
2 Correct 480 ms 155040 KB Output is correct
3 Correct 684 ms 207168 KB Output is correct
4 Correct 808 ms 268024 KB Output is correct
5 Correct 1067 ms 270456 KB Output is correct
6 Correct 736 ms 265976 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 14 ms 3456 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 14 ms 3384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 15 ms 3456 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 16 ms 3456 KB Output is correct
10 Correct 851 ms 267896 KB Output is correct
11 Correct 868 ms 268000 KB Output is correct
12 Correct 482 ms 128276 KB Output is correct
13 Correct 480 ms 155040 KB Output is correct
14 Correct 684 ms 207168 KB Output is correct
15 Correct 808 ms 268024 KB Output is correct
16 Correct 1067 ms 270456 KB Output is correct
17 Correct 736 ms 265976 KB Output is correct
18 Correct 1064 ms 270588 KB Output is correct
19 Correct 907 ms 270344 KB Output is correct
20 Correct 909 ms 263800 KB Output is correct
21 Correct 755 ms 268024 KB Output is correct
22 Correct 1147 ms 270588 KB Output is correct