#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+2;
int aib[N], dp[N], n, a[N];
set<int>LIS[N];
void update (int x, int val) {
for (int i = x; i <= n; i += (i & -i))
aib[i] = max(aib[i],val);
}
int query (int x) {
int s= 0;
for (int i = x; i; i -= (i & -i))
s = max(s, aib[i]);
return s;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
int mx = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[i] = x;
dp[i] = query(x) + 1;
update(x, dp[i]);
LIS[dp[i]].insert(i);
mx = max(mx, dp[i]);
}
vector<vector<int>>ans;
while (LIS[mx].size()) {
int last = *LIS[mx].begin();
LIS[mx].erase(last);
vector<int>sir;
sir.push_back(last);
for (int i = mx - 1; i >= 1; i--) {
bool gasit = 0;
for (auto it : LIS[i]) {
if (it < last && a[it] < a[last]) {
last = it;
sir.push_back(last);
gasit = 1;
break;
}
}
LIS[i].erase(last);
if (!gasit)
break;
}
if (sir.size() < mx) continue;
reverse(sir.begin(), sir.end());
ans.push_back(sir);
}
cout << ans.size() << " " << ans[0].size() << "\n";
for (auto s : ans) {
for (auto it : s)
cout << it << " ";
cout << "\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:54:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | if (sir.size() < mx) continue;
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47196 KB |
Output is correct |
2 |
Correct |
15 ms |
47192 KB |
Output is correct |
3 |
Correct |
16 ms |
47696 KB |
Output is correct |
4 |
Correct |
17 ms |
47192 KB |
Output is correct |
5 |
Correct |
15 ms |
47196 KB |
Output is correct |
6 |
Correct |
16 ms |
47196 KB |
Output is correct |
7 |
Correct |
15 ms |
47192 KB |
Output is correct |
8 |
Correct |
16 ms |
47444 KB |
Output is correct |
9 |
Correct |
19 ms |
47436 KB |
Output is correct |
10 |
Correct |
17 ms |
47452 KB |
Output is correct |
11 |
Correct |
15 ms |
47192 KB |
Output is correct |
12 |
Correct |
15 ms |
47196 KB |
Output is correct |
13 |
Correct |
16 ms |
47344 KB |
Output is correct |
14 |
Correct |
16 ms |
47452 KB |
Output is correct |
15 |
Correct |
16 ms |
47196 KB |
Output is correct |
16 |
Correct |
16 ms |
47452 KB |
Output is correct |
17 |
Correct |
17 ms |
47384 KB |
Output is correct |
18 |
Correct |
17 ms |
47192 KB |
Output is correct |
19 |
Correct |
17 ms |
47196 KB |
Output is correct |
20 |
Correct |
17 ms |
47428 KB |
Output is correct |
21 |
Correct |
18 ms |
47196 KB |
Output is correct |
22 |
Correct |
17 ms |
47452 KB |
Output is correct |
23 |
Correct |
17 ms |
47196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47196 KB |
Output is correct |
2 |
Correct |
15 ms |
47192 KB |
Output is correct |
3 |
Correct |
16 ms |
47696 KB |
Output is correct |
4 |
Correct |
17 ms |
47192 KB |
Output is correct |
5 |
Correct |
15 ms |
47196 KB |
Output is correct |
6 |
Correct |
16 ms |
47196 KB |
Output is correct |
7 |
Correct |
15 ms |
47192 KB |
Output is correct |
8 |
Correct |
16 ms |
47444 KB |
Output is correct |
9 |
Correct |
19 ms |
47436 KB |
Output is correct |
10 |
Correct |
17 ms |
47452 KB |
Output is correct |
11 |
Correct |
15 ms |
47192 KB |
Output is correct |
12 |
Correct |
15 ms |
47196 KB |
Output is correct |
13 |
Correct |
16 ms |
47344 KB |
Output is correct |
14 |
Correct |
16 ms |
47452 KB |
Output is correct |
15 |
Correct |
16 ms |
47196 KB |
Output is correct |
16 |
Correct |
16 ms |
47452 KB |
Output is correct |
17 |
Correct |
17 ms |
47384 KB |
Output is correct |
18 |
Correct |
17 ms |
47192 KB |
Output is correct |
19 |
Correct |
17 ms |
47196 KB |
Output is correct |
20 |
Correct |
17 ms |
47428 KB |
Output is correct |
21 |
Correct |
18 ms |
47196 KB |
Output is correct |
22 |
Correct |
17 ms |
47452 KB |
Output is correct |
23 |
Correct |
17 ms |
47196 KB |
Output is correct |
24 |
Correct |
17 ms |
47452 KB |
Output is correct |
25 |
Correct |
16 ms |
47452 KB |
Output is correct |
26 |
Correct |
17 ms |
47488 KB |
Output is correct |
27 |
Correct |
17 ms |
47452 KB |
Output is correct |
28 |
Correct |
16 ms |
47452 KB |
Output is correct |
29 |
Correct |
18 ms |
47512 KB |
Output is correct |
30 |
Correct |
21 ms |
47708 KB |
Output is correct |
31 |
Correct |
17 ms |
47448 KB |
Output is correct |
32 |
Correct |
17 ms |
47452 KB |
Output is correct |
33 |
Incorrect |
17 ms |
47512 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
47196 KB |
Output is correct |
2 |
Correct |
15 ms |
47192 KB |
Output is correct |
3 |
Correct |
16 ms |
47696 KB |
Output is correct |
4 |
Correct |
17 ms |
47192 KB |
Output is correct |
5 |
Correct |
15 ms |
47196 KB |
Output is correct |
6 |
Correct |
16 ms |
47196 KB |
Output is correct |
7 |
Correct |
15 ms |
47192 KB |
Output is correct |
8 |
Correct |
16 ms |
47444 KB |
Output is correct |
9 |
Correct |
19 ms |
47436 KB |
Output is correct |
10 |
Correct |
17 ms |
47452 KB |
Output is correct |
11 |
Correct |
15 ms |
47192 KB |
Output is correct |
12 |
Correct |
15 ms |
47196 KB |
Output is correct |
13 |
Correct |
16 ms |
47344 KB |
Output is correct |
14 |
Correct |
16 ms |
47452 KB |
Output is correct |
15 |
Correct |
16 ms |
47196 KB |
Output is correct |
16 |
Correct |
16 ms |
47452 KB |
Output is correct |
17 |
Correct |
17 ms |
47384 KB |
Output is correct |
18 |
Correct |
17 ms |
47192 KB |
Output is correct |
19 |
Correct |
17 ms |
47196 KB |
Output is correct |
20 |
Correct |
17 ms |
47428 KB |
Output is correct |
21 |
Correct |
18 ms |
47196 KB |
Output is correct |
22 |
Correct |
17 ms |
47452 KB |
Output is correct |
23 |
Correct |
17 ms |
47196 KB |
Output is correct |
24 |
Correct |
17 ms |
47452 KB |
Output is correct |
25 |
Correct |
16 ms |
47452 KB |
Output is correct |
26 |
Correct |
17 ms |
47488 KB |
Output is correct |
27 |
Correct |
17 ms |
47452 KB |
Output is correct |
28 |
Correct |
16 ms |
47452 KB |
Output is correct |
29 |
Correct |
18 ms |
47512 KB |
Output is correct |
30 |
Correct |
21 ms |
47708 KB |
Output is correct |
31 |
Correct |
17 ms |
47448 KB |
Output is correct |
32 |
Correct |
17 ms |
47452 KB |
Output is correct |
33 |
Incorrect |
17 ms |
47512 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |