Submission #1267496

---

Source Code Expand

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct Node {
	Node *l = 0, *r = 0;
	int val, y;
	int first, max;
	bool monotone;
	Node(int val) : val(val), y(rand()) {
		first = max = val;
		monotone = 1;
	}
	void reset() {
		first = max = val;
		monotone = 1;
	}
	void recalc();
	void recalc3();
};

inline void Node::recalc() {
	first = l ? l->first : val;
	int max = val;
	bool mon = 1;
	if (l) {
		max = std::max(max, l->max);
		if (!l->monotone || l->max > val) mon = 0;
	}
	if (r) {
		max = std::max(max, r->max);
		if (mon && (!r->monotone || r->first < val)) mon = 0;
	}
	this->max = max;
	monotone = mon;
}

inline void Node::recalc3() {
	first = l ? l->first : val;
	int max = val;
	if (l) {
		max = std::max(max, l->max);
	}
	if (r) {
		max = std::max(max, r->max);
	}
	this->max = max;
	monotone = 1;
}

Node* merge2(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge2(l->r, r) : r;
		l->recalc();
		return l;
	} else {
		r->l = r->l ? merge2(l, r->l) : l;
		r->recalc();
		return r;
	}
}

inline Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge2(l, r);
}

Node* merge32(Node* l, Node* r) {
	if (l->y > r->y) {
		l->r = l->r ? merge32(l->r, r) : r;
		l->recalc3();
		return l;
	} else {
		r->l = r->l ? merge32(l, r->l) : l;
		r->recalc3();
		return r;
	}
}

inline Node* merge3(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	return merge32(l, r);
}

pair<Node*, Node*> split2(Node* n, int lo) {
	if (!n) return {0, 0};
	if (n->max < lo) return {0, n};
	if (n->monotone) {
		if (lo < n->first) return {n, 0};
		if (!n->l) {
			if (!n->r) return {0, n};
			assert(lo >= n->val);
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->reset();
			pa.second = merge(n, pa.second);
			return pa;
		}

		if (lo < n->val) {
			auto pa = split2(n->l, lo);
			n->l = 0;
			n->recalc();
			pa.first = merge3(pa.first, n);
			return pa;
		}
		else {
			// if (!n->r) return {0, n};
			auto pa = split2(n->r, lo);
			n->r = 0;
			n->recalc();
			pa.second = merge(n, pa.second);
			return pa;
		}
	}

	Node *left = n->l, *right = n->r;
	n->l = n->r = 0;
	n->recalc();
	auto pa = split2(left, lo);
	if (pa.first) lo = pa.first->max;
	if (n->val > lo) {
		pa.first = merge3(pa.first, n);
		lo = n->val;
	}
	else {
		pa.second = merge(pa.second, n);
	}
	auto pa2 = split2(right, lo);
	return {merge3(pa.first, pa2.first), merge(pa.second, pa2.second)};
}

int main() {
	srand(2);
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int N;
	cin >> N;
	vector<Node> nodes;
	rep(i,0,N) {
		int p;
		cin >> p;
		nodes.emplace_back(p);
	}

	Node* t = 0;
	rep(i,0,N)
		t = merge(t, &nodes[i]);

	int res = 0;
	while (!t->monotone) {
		++res;
		auto pa = split2(t, 0);
		t = merge(pa.second, pa.first);
	}

	cout << res << endl;
	exit(0);
}

Submission Info

Judge Result