oj.uz

Submission #855227

# Submission time Handle Problem Language Result Execution time Memory
855227 2023-09-30T21:50:03 Z NK_ Editor (BOI15_edi) C++17
100 / 100
 396 ms 228260 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;
			R.pb(R[prv]->upd(-A[i], i));
		}
		cout << A[R.back()->qry(0, 0)] << nl;
	}

	exit(0-0);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33116 KB Output is correct
2 Correct 36 ms 36432 KB Output is correct
3 Correct 30 ms 33104 KB Output is correct
4 Correct 31 ms 33116 KB Output is correct
5 Correct 35 ms 36408 KB Output is correct
6 Correct 30 ms 33160 KB Output is correct
7 Correct 34 ms 36436 KB Output is correct
8 Correct 35 ms 33232 KB Output is correct
9 Correct 36 ms 36444 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 228260 KB Output is correct
2 Correct 272 ms 226748 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 129728 KB Output is correct
2 Correct 193 ms 149000 KB Output is correct
3 Correct 266 ms 186904 KB Output is correct
4 Correct 273 ms 227260 KB Output is correct
5 Correct 390 ms 228024 KB Output is correct
6 Correct 263 ms 226748 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33116 KB Output is correct
2 Correct 36 ms 36432 KB Output is correct
3 Correct 30 ms 33104 KB Output is correct
4 Correct 31 ms 33116 KB Output is correct
5 Correct 35 ms 36408 KB Output is correct
6 Correct 30 ms 33160 KB Output is correct
7 Correct 34 ms 36436 KB Output is correct
8 Correct 35 ms 33232 KB Output is correct
9 Correct 36 ms 36444 KB Output is correct
10 Correct 277 ms 228260 KB Output is correct
11 Correct 272 ms 226748 KB Output is correct
12 Correct 185 ms 129728 KB Output is correct
13 Correct 193 ms 149000 KB Output is correct
14 Correct 266 ms 186904 KB Output is correct
15 Correct 273 ms 227260 KB Output is correct
16 Correct 390 ms 228024 KB Output is correct
17 Correct 263 ms 226748 KB Output is correct
18 Correct 357 ms 227396 KB Output is correct
19 Correct 308 ms 226816 KB Output is correct
20 Correct 348 ms 225964 KB Output is correct
21 Correct 272 ms 227188 KB Output is correct
22 Correct 396 ms 227260 KB Output is correct