Submission #862201

#	Time	Username	Problem	Language	Result	Execution time	Memory
862201		TAhmed33	Volontiranje (COCI21_volontiranje)	C++98	50 / 110	100 ms	604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
pair <int, int> comp (pair <int, int> a, pair <int, int> b) {
	if (a.first == b.first) return a.second < b.second ? a : b;
	return a.first < b.first ? b : a;
}
struct SegmentTree {
	pair <int, int> tree[2001];
	void update (int l, int r, int a, pair <int, int> b, int node) {
		if (l > a || r < a) return;
		if (l == r) {
			tree[node] = comp(tree[node], b);
			return;
		}
		update(l, mid, a, b, tl);
		update(mid + 1, r, a, b, tr);
		tree[node] = comp(tree[tl], tree[tr]);
	}
	pair <int, int> get (int l, int r, int a, int b, int node) {
		if (a > b) return {0, 0};
		if (l > b || r < a) return {0, 0};
		if (l >= a && r <= b) return tree[node];
		return comp(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
};
int arr[1001];
int n;
int main () {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	bool active[n + 1];
	for (int i = 1; i <= n; i++) active[i] = 1;
	vector <vector <int>> ans;
	int mx = 0;
	while (true) {
		int dp[n + 1] = {}, par[n + 1] = {};
		SegmentTree p; int l = 0;
		for (int i = 1; i <= n; i++) {
			if (!active[i]) continue;
			auto t = p.get(1, n, 1, arr[i] - 1, 1);
			dp[i] = t.first + 1;
			par[i] = t.second; l = max(l, dp[i]);
			p.update(1, n, arr[i], {dp[i], i}, 1);
		}
		if (l < mx) break;
		mx = l;
		bool ok[n + 1]; memset(ok, 0, sizeof(ok));
		int nxt[n + 1] = {};
		for (int i = n; i >= 1; i--) {
			if (!active[i]) continue;
			if (dp[i] == l) ok[i] = 1;
			if (!ok[i]) continue;
			ok[par[i]] = 1;
			nxt[par[i]] = i;
		}
		vector <int> u;
		for (int i = 1; i <= n; i++) {
			if (!active[i]) continue;
			if (ok[i]) {
				while (dp[i] != l) {
					u.push_back(i);
					active[i] = 0;
					i = nxt[i];
				}
				u.push_back(i);
				active[i] = 0;
				break;
			}
		}
		ans.push_back(u);
	}
	cout << ans.size() << " " << mx << '\n';
	for (auto i : ans) {
		for (auto j : i) cout << j << " ";
		cout << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 60