oj.uz

Submission #658391

# Submission time Handle Problem Language Result Execution time Memory
658391 2022-11-13T04:58:41 Z Foxyy Volontiranje (COCI21_volontiranje) C++17
0 / 110
 1 ms 212 KB 
#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());
			for (auto i : indiciesOfLength[len]) {
				while (cur >= 0 and indiciesOfLength[len-1][cur] > i) {
					cur--;
				}
				if (cur < 0) break;
				if (a[i] < a[indiciesOfLength[len-1][cur]]) {
					continue;
				}
				lst[i] = indiciesOfLength[len-1][cur];
				cur--;
			}
		}
		
//		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);
			}
			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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -