Submission #855224

#	Time	Username	Problem	Language	Result	Execution time	Memory
855224		NK_	Editor (BOI15_edi)	C++17	15 / 100	684 ms	229200 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; 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(-1); vr = new node(-1); 
		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(-1)};
	R.back()->build();

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

		cout << A[R.back()->qry(0, 0) - 1] << endl;
	}

	exit(0-0);
} 	 

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