Submission #855227

#	Time	Username	Problem	Language	Result	Execution time	Memory
855227		NK_	Editor (BOI15_edi)	C++17	100 / 100	396 ms	228260 KiB

edi

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

const int nax = (1<<19) - 1;

struct node {
	int mx = 0; node *vl, *vr;

	node(int v) : mx(v), vl(nullptr), vr(nullptr) {}

	node(node *_vl, node *_vr) : vl(_vl), vr(_vr) {
		if (vl) mx = max(mx, vl->mx);
		if (vr) mx = max(mx, vr->mx);
	}

	void build(int L = 0, int R = nax) {
		if (L == R) return;
		int M = (L + R) / 2;
		vl = new node(0); vr = new node(0); 
		vl->build(L, M); vr->build(M+1, R);
	};

	int qry(int l, int r, int L = 0, int R = nax) {
		// cout << L << " " << R << endl;
		if (r < L || R < l) return 0;
		if (l <= L && R <= r) return mx;

		int M = (L + R) / 2;
		return max(vl->qry(l, r, L, M), vr->qry(l, r, M + 1, R));
	}

	node* upd(int pos, int x, int L = 0, int R = nax) {
		if (L == R) return new node(x);

		int M = (L + R) / 2;
		if (pos <= M) return new node(vl->upd(pos, x, L, M), vr);
		else return new node(vl, vr->upd(pos, x, M+1, R));
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;

	V<node*> R = {new node(0)};
	R.back()->build();

	vi A(N+1); A[0] = 0;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		if (A[i] > 0) R.pb(R.back()->upd(0, i));
		else {
			int prv = R.back()->qry(0, -A[i] - 1) - 1;
			R.pb(R[prv]->upd(-A[i], i));
		}
		cout << A[R.back()->qry(0, 0)] << nl;
	}

	exit(0-0);
} 	 

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