Submission #862256

#	Time	Username	Problem	Language	Result	Execution time	Memory
862256		Cyber_Wolf	Volontiranje (COCI21_volontiranje)	C++17	10 / 110	106 ms	4696 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")

using namespace std;
using namespace __gnu_pbds;

#define lg long long
#define ordered_set	tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mid (lr+hr)/2

const lg N = 1e6+5;

lg n;
lg seg[N << 2], dp[N], loc[N], v[N], best[N];

void upd(lg node, lg lr, lg hr, lg idx, lg val)
{
	if(lr > idx || hr < idx)	return;
	if(lr == hr)
	{
		seg[node] = val;
		return;
	}
	upd(node << 1, lr, mid, idx, val);
	upd(node << 1 | 1, mid+1, hr, idx, val);
	seg[node] = seg[node << 1 | 1];
	if(dp[seg[node << 1]] > dp[seg[node << 1 | 1]])
	{
		seg[node] = seg[node << 1];
	}
	return;
}

lg get(lg node, lg lr, lg hr, lg lq, lg hq)
{
	if(lq > hr || lr > hq)	return 0;
	if(lq <= lr && hr <= hq)
	{
		return seg[node];
	}
	lg l = get(node << 1, lr, mid, lq, hq);
	lg r = get(node << 1 | 1, mid+1, hr, lq, hq);
	lg ans = r;
	if(dp[l] > dp[r])	ans = l;
	return ans;
}

int main()
{
	fastio;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i];
		loc[v[i]] = i;
	}
	lg ans = 0;
	for(int i = 1; i <= n; i++)
	{
		lg idx = get(1, 1, n, 1, v[i]);
		dp[i] = dp[idx]+1;
		upd(1, 1, n, v[i], i);
		ans = max(ans, dp[i]);
		best[i] = idx;
	}
	vector<vector<lg>> an;
	while(true)
	{
		for(int i = n; i >= 1; i--)
		{
			if(dp[i] == ans)
			{
				lg idx = i;
				vector<lg> o;
				while(idx)
				{
					o.push_back(idx);
					v[idx] = 0;
					idx = best[idx];
				}
				reverse(o.begin(), o.end());
				an.push_back(o);
				break;
			}
		}
		for(int i = 1; i <= n; i++)	upd(1, 1, n, i, 0), dp[i] = best[i] = 0;
		lg mxm = 0;
		for(int i = 1; i <= n; i++)
		{
			if(!v[i])	continue;
			lg idx = get(1, 1, n, 1, v[i]);
			dp[i] = dp[idx]+1;
			upd(1, 1, n, v[i], i);
			mxm = max(mxm, dp[i]);
			best[i] = idx;
		}
		if(mxm != ans)	break;
	}
	cout << an.size() << ' ' << ans << '\n';
	for(auto it : an)
	{
		for(auto it2 : it)	cout << it2 << ' ';
		cout << '\n';
	}

    return 0;
}

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