Submission #658396

#	Time	Username	Problem	Language	Result	Execution time	Memory
658396		Foxyy	Volontiranje (COCI21_volontiranje)	C++17	10 / 110	1 ms	340 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);

template <typename T>
struct PrefixSum {
	int n;
	vector<T> sum;
	
	PrefixSum() {}
	PrefixSum(vector<int> vec) : n((int)vec.size()) {
		sum.resize(n+1);
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i-1] + vec[i-1];
		}
	};
	
	T getSum(int l, int r) {
		return sum[r+1] - sum[l];
	}
};

struct Solver {
	int& n;
	vector<int>& a;
	
	void solve() {
		vector<int> l(n);
		vector<int> lis;
		for (int i = 0; i < n; i++) {
			auto it = lower_bound(lis.begin(), lis.end(), a[i]);
			l[i] = it - lis.begin();
			if (it == lis.end()) {
				lis.push_back(a[i]);
			} else {
				*it = a[i];
			}
		}
		
		vector<vector<int>> indiciesOfLength((int)lis.size());
		for (int i = 0; i < n; i++) {
			indiciesOfLength[l[i]].push_back(i);
		}
		
		vector<int> lst(n, -1);
		for (int len = (int)lis.size()-1; len > 0; len--) {
			int cur = (int)indiciesOfLength[len-1].size() - 1;
			reverse(indiciesOfLength[len].begin(), indiciesOfLength[len].end());
			vector<int> tmp;
			for (auto i : indiciesOfLength[len]) {
				while (cur >= 0 and indiciesOfLength[len-1][cur] > i) {
					cur--;
				}
				if (cur < 0) break;
				if (a[indiciesOfLength[len-1][cur]] > a[i]) continue;
				lst[i] = indiciesOfLength[len-1][cur];
				tmp.push_back(indiciesOfLength[len-1][cur]);
				cur--;
			}
			reverse(tmp.begin(), tmp.end());
			indiciesOfLength[len-1] = tmp;
		}
		
//		for (int i = 0; i < n; i++) {
//			cerr << i << ' ' << a[i] << ' ' << l[i] << ' ' << lst[i] << '\n';
//		}
		
		vector<vector<int>> ans;
		for (auto ind : indiciesOfLength[(int)lis.size()-1]) {
			vector<int> vec{ind};
			while (lst[ind] != -1) {
				ind = lst[ind];
				vec.push_back(ind);
			}
			if (vec.size() != lis.size()) {
				continue;
			}
			reverse(vec.begin(), vec.end());
			ans.push_back(vec);
		}
		
		cout << (int)ans.size() << ' ' << (int)lis.size() << '\n';
		for (auto vec : ans) {
			for (auto x : vec) {
				cout << x+1 << ' ';
			}
			cout << '\n';
		}
	}
};

signed main() {
	Foxyy
	
	int T = 1;
//	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto& x : a) {
			cin >> x;
		}
		
		Solver solver{n, a};
		solver.solve();
	}
}

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