oj.uz

Submission #862256

# Submission time Handle Problem Language Result Execution time Memory
862256 2023-10-17T21:07:34 Z Cyber_Wolf Volontiranje (COCI21_volontiranje) C++17
10 / 110
 106 ms 4696 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 2 ms 4444 KB Output is correct
27 Correct 1 ms 4440 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 106 ms 4440 KB Output is correct
31 Correct 4 ms 4444 KB Output is correct
32 Correct 4 ms 4444 KB Output is correct
33 Incorrect 33 ms 4444 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4696 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 2 ms 4444 KB Output is correct
27 Correct 1 ms 4440 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 106 ms 4440 KB Output is correct
31 Correct 4 ms 4444 KB Output is correct
32 Correct 4 ms 4444 KB Output is correct
33 Incorrect 33 ms 4444 KB Output isn't correct
34 Halted 0 ms 0 KB -