#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
struct SEGT{
vector < int > tree;
int sz;
SEGT(int x){
x += 5;
sz = x;
tree.assign(4 * sz , 0);
}
void _update(int ind , int l , int r , int qp , int qv){
if(l == r){
tree[ind] = qv;
return;
}
int mid = (l+r)/2;
if(mid >= qp){
_update(ind*2,l,mid,qp,qv);
}
else{
_update(ind*2+1,mid+1,r,qp,qv);
}
tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
}
void update(int p , int v){
_update(1,1,sz,p,v);
}
int _query(int ind , int l , int r , int ql , int qr){
if(l >= ql and r <= qr){
return tree[ind];
}
else if(l > qr or r < ql){
return 0;
}
else{
int mid = (l+r)/2;
return max(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
}
}
int query(int l , int r){
return _query(1,1,sz,l,r);
}
};
int n,arr[N],lis[N],nxt[N],mx = 0;
vector < pair < int , int > > rq[N];
stack < pair < int , int > > q[N];
vector < vector < int > > ans;
vector < int > locans;
inline bool dfs(int node){
//cout << node << " " << arr[node] << endl;
if(lis[node] == 1){
locans.push_back(node);
if(mx == 1){
ans.push_back(locans);
locans.clear();
}
return 1;
}
bool work = 0;
while(q[lis[node]-1].size()){
pair < int , int > cand = q[lis[node]-1].top();
if(cand.first < node and cand.second < arr[node]){
bool bl = dfs(cand.first);
if(bl){
work = 1;
locans.push_back(node);
q[lis[node]-1].pop();
break;
}
else{
q[lis[node]-1].pop();
}
}
else if(cand.first > node and cand.second < arr[node]){
q[lis[node]-1].pop();
}
else if(cand.first < node and cand.second > arr[node]){
break;
}
}
if(work == 0){
return 0;
}
else if(work == 1 and lis[node] == mx){
ans.push_back(locans);
locans.clear();
}
return 1;
}
void solve(){
memset(nxt , -1 , sizeof(nxt));
cin >> n;
SEGT segt(n);
//cout << "flag0" << endl;
for(int i = 0;i<n;i++){
cin >> arr[i];
lis[i] = segt.query(1,arr[i]) + 1;
mx = max(mx , lis[i]);
rq[lis[i]].push_back({i,arr[i]});
segt.update(arr[i],lis[i]);
}
for(int i = 0;i<N;i++){
sort(rq[i].begin() , rq[i].end());
for(auto itr : rq[i]){
q[i].push(itr);
}
}
while(q[mx].size()){
dfs(q[mx].top().first);
q[mx].pop();
}
cout << ans.size() << " " << mx << endl;
for(auto itr : ans){
for(auto itr1 : itr){
cout << itr1+1 << " ";
}
cout << endl;
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
272 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
