oj.uz

Submission #855226

# Submission time Handle Problem Language Result Execution time Memory
855226 2023-09-30T21:47:50 Z NK_ Editor (BOI15_edi) C++17
100 / 100
 713 ms 230300 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 = 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;
			// 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33108 KB Output is correct
2 Correct 38 ms 36436 KB Output is correct
3 Correct 28 ms 33120 KB Output is correct
4 Correct 28 ms 33224 KB Output is correct
5 Correct 39 ms 36432 KB Output is correct
6 Correct 28 ms 33068 KB Output is correct
7 Correct 38 ms 36432 KB Output is correct
8 Correct 29 ms 33272 KB Output is correct
9 Correct 39 ms 36432 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 227504 KB Output is correct
2 Correct 601 ms 227376 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 129892 KB Output is correct
2 Correct 380 ms 149004 KB Output is correct
3 Correct 535 ms 188320 KB Output is correct
4 Correct 687 ms 229048 KB Output is correct
5 Correct 706 ms 230208 KB Output is correct
6 Correct 666 ms 227144 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33108 KB Output is correct
2 Correct 38 ms 36436 KB Output is correct
3 Correct 28 ms 33120 KB Output is correct
4 Correct 28 ms 33224 KB Output is correct
5 Correct 39 ms 36432 KB Output is correct
6 Correct 28 ms 33068 KB Output is correct
7 Correct 38 ms 36432 KB Output is correct
8 Correct 29 ms 33272 KB Output is correct
9 Correct 39 ms 36432 KB Output is correct
10 Correct 604 ms 227504 KB Output is correct
11 Correct 601 ms 227376 KB Output is correct
12 Correct 396 ms 129892 KB Output is correct
13 Correct 380 ms 149004 KB Output is correct
14 Correct 535 ms 188320 KB Output is correct
15 Correct 687 ms 229048 KB Output is correct
16 Correct 706 ms 230208 KB Output is correct
17 Correct 666 ms 227144 KB Output is correct
18 Correct 713 ms 230300 KB Output is correct
19 Correct 647 ms 228720 KB Output is correct
20 Correct 659 ms 227312 KB Output is correct
21 Correct 614 ms 228708 KB Output is correct
22 Correct 712 ms 228792 KB Output is correct