#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
pair <int, int> comp (pair <int, int> a, pair <int, int> b) {
if (a.first == b.first) return a.second < b.second ? a : b;
return a.first < b.first ? b : a;
}
struct SegmentTree {
pair <int, int> tree[2001];
void update (int l, int r, int a, pair <int, int> b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = comp(tree[node], b);
return;
}
update(l, mid, a, b, tl);
update(mid + 1, r, a, b, tr);
tree[node] = comp(tree[tl], tree[tr]);
}
pair <int, int> get (int l, int r, int a, int b, int node) {
if (a > b) return {0, 0};
if (l > b || r < a) return {0, 0};
if (l >= a && r <= b) return tree[node];
return comp(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
}
};
int arr[1001];
int n;
int main () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
bool active[n + 1];
for (int i = 1; i <= n; i++) active[i] = 1;
vector <vector <int>> ans;
int mx = 0;
while (true) {
int dp[n + 1] = {}, par[n + 1] = {};
SegmentTree p; int l = 0;
for (int i = 1; i <= n; i++) {
if (!active[i]) continue;
auto t = p.get(1, n, 1, arr[i] - 1, 1);
dp[i] = t.first + 1;
par[i] = t.second; l = max(l, dp[i]);
p.update(1, n, arr[i], {dp[i], i}, 1);
}
if (l < mx) break;
mx = l;
bool ok[n + 1]; memset(ok, 0, sizeof(ok));
int nxt[n + 1] = {};
for (int i = n; i >= 1; i--) {
if (!active[i]) continue;
if (dp[i] == l) ok[i] = 1;
if (!ok[i]) continue;
ok[par[i]] = 1;
nxt[par[i]] = i;
}
vector <int> u;
for (int i = 1; i <= n; i++) {
if (!active[i]) continue;
if (ok[i]) {
while (dp[i] != l) {
u.push_back(i);
active[i] = 0;
i = nxt[i];
}
u.push_back(i);
active[i] = 0;
break;
}
}
ans.push_back(u);
}
cout << ans.size() << " " << mx << '\n';
for (auto i : ans) {
for (auto j : i) cout << j << " ";
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
