oj.uz

Submission #512930

# Submission time Handle Problem Language Result Execution time Memory
512930 2022-01-16T20:08:54 Z sidon Teams (CEOI11_tea) C++17
100 / 100
 915 ms 85620 KB 
#include <bits/stdc++.h>
using namespace std;
using T = array<int, 2>;

class comp{
public:
	bool operator()(const T &x, const T &y) {
		return x[0] < y[0];
	}
};
 
const int Z = 1e6+1, oo = 2e9;
 
int N, A[Z], S[Z], P[Z];
array<int, 2> DP[Z];
 
const T ID = {-oo, -1};
 
void build(int x) {
	priority_queue<array<int, 2>, vector<T>, comp> b;
	int r = 0;
	b.push(DP[0]);
 
	for(int i = 1; i <= N; i++) {
		int R = max(-1, i - A[S[i]]);
 
		while(r < R) b.push(DP[++r]);
		r = R;
 
		while(!empty(b) && (b.top()[1] < i - x || b.top()[1] > R)) b.pop();
 
		if(empty(b)) {
			DP[i] = ID;
		} else {
			DP[i] = b.top();
			P[i] = DP[i][1];
			DP[i][1] = i;
			++DP[i][0];
		}
	}
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> N;
 
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		S[i] = i;
	}
 
	fill(DP, DP+Z, ID);
	DP[0] = {};
 
	sort(S, S + N + 1, [&](int i, int j) {
		return A[i] < A[j];
	});
 
	build(1e6);
 
	int best = DP[N][0], sz = N;
 
	for(int j=1<<20; j/=2; ) {
		if(sz - j < A[S[N]]) continue;
		build(sz - j);
		if(DP[N][0] == best) sz -= j;
	}
 
	build(sz);
 
	int curr = P[N];
 
	vector<vector<int>> res = {{}};
 
	for(int i = N + 1; --i; ) {
		if(curr == i) {
			res.push_back({});
			curr = P[curr];
		}
		res.back().push_back(S[i]);
	}
 
	cout << size(res) << '\n';
	for(auto &V : res) {
		cout << size(V);
		for(auto &i : V) cout << ' ' << i;
		cout << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8124 KB Output is correct
5 Correct 3 ms 8140 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8124 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8084 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8128 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 4 ms 8124 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8312 KB Output is correct
2 Correct 6 ms 8304 KB Output is correct
3 Correct 5 ms 8268 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8272 KB Output is correct
2 Correct 6 ms 8220 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10492 KB Output is correct
2 Correct 46 ms 10984 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 11344 KB Output is correct
2 Correct 42 ms 10904 KB Output is correct
3 Correct 42 ms 11252 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 34660 KB Output is correct
2 Correct 434 ms 33232 KB Output is correct
3 Correct 425 ms 34988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 40920 KB Output is correct
2 Correct 915 ms 85620 KB Output is correct
3 Correct 711 ms 38840 KB Output is correct
4 Correct 483 ms 38148 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 39132 KB Output is correct
2 Correct 190 ms 34636 KB Output is correct
3 Correct 609 ms 39800 KB Output is correct
4 Correct 914 ms 41216 KB Output is correct