제출 #1191451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191451		kl0989e	Editor (BOI15_edi)	C++20	15 / 100	86 ms	14152 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 mn=1e9;
		int ind=-1;
	};
	node unite(node a, node b) {
		if (b.mn<=a.mn) {
			return b;
		}
		return a;
	}

	vector<node> nodes;
	int sze;

	segTree(int n): sze(n) {
		nodes.resize(4*sze);
		build(1,0,sze-1);
	}

	void build(int v, int tl, int tr) {
		if (tl==tr) {
			nodes[v].ind=tl;
			return;
		}
		int tm=tl+(tr-tl)/2;
		build(2*v,tl,tm);
		build(2*v+1,tm+1,tr);
		nodes[v]=unite(nodes[2*v],nodes[2*v+1]);
	}

	void update(int val, int ind, int v, int tl, int tr) {
		if (ind<tl || tr<ind) {
			return;
		}
		if (tl==tr) {
			nodes[v].mn=val;
			return;
		}
		int tm=tl+(tr-tl)/2;
		update(val,ind,2*v,tl,tm);
		update(val,ind,2*v+1,tm+1,tr);
		nodes[v]=unite(nodes[2*v],nodes[2*v+1]);
	}
	void update(int val, int ind) {
		update(val,ind,1,0,sze-1);
	}

	node get(int ind, int v, int tl, int tr) {
		if (tl==tr) {
			return nodes[v];
		}
		int tm=tl+(tr-tl)/2;
		if (nodes[2*v+1].mn>=ind) {
			return get(ind,2*v,tl,tm);
		}
		return get(ind,2*v+1,tm+1,tr);
	}
	node get(int ind) {
		return get(ind,1,0,sze-1);
	}
};

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	stack<int> stk;
	stk.push(0);
	vi nums(n);
	vi to(n);
	segTree data(n);
	int a;
	for (int i=0; i<n; i++) {
		cin >> a;
		if (a>0) {
			stk.push(a);
			nums[i]=-1;
			to[i]=i;
			data.update(0,i);
		}
		else {
			auto t=data.get(-a);
			data.update(-a,i);
			to[i]=to[t.ind];
			if (nums[to[i]]==-1) {
				nums[to[i]]=stk.top();
				stk.pop();
				data.update(1e9,to[i]);
			}
			else {
				stk.push(nums[to[i]]);
				nums[to[i]]=-1;
				data.update(0,to[i]);
			}
		}
		cout << stk.top() << '\n';
	}
	return 0;
}

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