Submission #1191484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191484		kl0989e	Editor (BOI15_edi)	C++20	100 / 100	232 ms	84776 KiB

edi

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

struct segTree {
    struct node {
    	int mx=-1;

        node() {};
        node(int _mx): mx(_mx) {}
    };

    node unite(node a, node b) {
        return {max(a.mx,b.mx)};
    }

    int newnode() {
        nodes.pb(node());
        l.pb(0);
        r.pb(0);
        return nodes.size()-1;
    }

    int n;
    vector<node> nodes;
    vi l,r;

    segTree(int _n): n(_n) {}

    void build(vl& a, int v, int tl, int tr) {
        if (tl==tr) {
            nodes[v]=a[tl];
        }
        else {
            int tm=tl+(tr-tl)/2;
            l[v]=newnode();
            r[v]=newnode();
            build(a,l[v],tl,tm);
            build(a,r[v],tm+1,tr);
            nodes[v]=unite(nodes[l[v]],nodes[r[v]]);
        }
    }
    int build(vl& a) {
        int v=newnode();
        build(a,v,0,n-1);
        return v;
    }

    void update(int pos, ll new_val, int v, int tl, int tr, int prev) {
        if (tl==tr) {
            nodes[v]=new_val;
        }
        else {
            int tm=tl+(tr-tl)/2;
            if (pos<=tm) {
                l[v]=newnode();
                r[v]=r[prev];
                update(pos,new_val,l[v],tl,tm,l[prev]);
            }
            else {
                l[v]=l[prev];
                r[v]=newnode();
                update(pos,new_val,r[v],tm+1,tr,r[prev]);
            }
            nodes[v]=unite(nodes[l[v]],nodes[r[v]]);
        }
    }
    int update(int pos, ll new_val, int prev) {
        int v=newnode();
        update(pos,new_val,v,0,n-1,prev);
        return v;
    }

    node get(int ql, int qr, int v, int tl, int tr) {
        if (ql<=tl && tr<=qr) {
            return nodes[v];
        }
        if (tr<ql || qr<tl) {
            return node();
        }
        int tm=tl+(tr-tl)/2;
        return unite(get(ql,qr,l[v],tl,tm),get(ql,qr,r[v],tm+1,tr));
    }
    node get(int l, int r, int rt) {
        return get(l,r,rt,0,n-1);
    }
};

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vi ans(n+1,0);
	segTree data(n+1);
	vi roots(n+1);
	vl t(n+1,-1);
	roots[0]=data.build(t);
	int a;
	for (int i=0; i<n; i++) {
		cin >> a;
		if (a>0) {
			roots[i+1]=data.update(0,i+1,roots[i]);
			ans[i+1]=a;
		}
		else {
			int t=data.get(0,-a-1,roots[i]).mx-1;
			roots[i+1]=data.update(-a,i+1,roots[t]);
			ans[i+1]=ans[t];
		}
		cout << ans[i+1] << '\n';
	}
	return 0;
}

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