oj.uz

Submission #855225

# Submission time Handle Problem Language Result Execution time Memory
855225 2023-09-30T21:46:56 Z NK_ Editor (BOI15_edi) C++17
15 / 100
 632 ms 228108 KB 
// 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(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;
			// cout << "PRV: " << prv << endl;
			R.pb(R[prv]->upd(-A[i], i));
		}
		cout << A[R.back()->qry(0, 0)] << endl;
	}

	exit(0-0);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33104 KB Output is correct
2 Runtime error 67 ms 72320 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 227664 KB Output is correct
2 Correct 632 ms 228108 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 129644 KB Output is correct
2 Correct 390 ms 149044 KB Output is correct
3 Runtime error 59 ms 69204 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33104 KB Output is correct
2 Runtime error 67 ms 72320 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -