#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;
pair <int,int> dp[DIM],v[DIM];
vector <int> sol[DIM],events[DIM];
vector <pair<int,int> > s;
int t[DIM],aint[DIM*4];
int n,i,j,k,maxim,ans;
void build (int nod, int st, int dr){
aint[nod] = INF;
if (st == dr)
return;
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
}
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod] = val;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
aint[nod] = min (aint[nod<<1],aint[(nod<<1)|1]);
}
void query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
ans = min (ans,aint[nod]);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++){
cin>>v[i].first;
v[i].second = i;
}
sort (v+1,v+n+1);
reverse (v+1,v+n+1);
/// dp[i] - nr maxim de secv in care pot imparti sirul si care e dimensiunea maxima minima
for (i=1;i<=n;i++)
dp[i] = make_pair(-INF,INF);
/// cand incepe sa aiba influenta un dp?
for (i=1;i<=n;i++)
events[i + v[i].first - 1].push_back(i-1);
build (1,0,n);
int maxim = -1;
for (i=1;i<=n;i++){
for (auto it : events[i]){
if (dp[it].first > maxim){
maxim = dp[it].first;
for (auto it2 : s)
update (1,0,n,it2.second,INF);
s.clear();
s.push_back(make_pair(dp[it].second,it));
update (1,0,n,it,dp[it].second);
} else {
if (dp[it].first == maxim){
s.push_back(make_pair(dp[it].second,it));
update (1,0,n,it,dp[it].second);
}}
}
if (maxim == -1)
continue;
/// calculez dp[i];
dp[i].first = maxim + 1;
/// caut binar dp[i].second
int st = 0, dr = i;
while (st <= dr){
int mid = (st+dr)>>1;
ans = INF;
query (1,0,n,i-mid,i-1);
if (ans <= mid){
dp[i].second = mid;
t[i] = i-mid;
dr = mid-1;
} else st = mid+1;
}
}
int x = n;
while (x > 0){
++k;
for (i=t[x]+1;i<=x;i++)
sol[k].push_back(v[i].second);
x = t[x];
}
cout<<k<<"\n";
for (i=1;i<=k;i++){
cout<<sol[i].size()<<" ";
for (auto it : sol[i])
cout<<it<<" ";
cout<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47180 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
47288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
47300 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
47180 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
47508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
47568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
263 ms |
53280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
318 ms |
53700 KB |
Output is correct |
| 2 |
Incorrect |
270 ms |
53088 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2542 ms |
92908 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2565 ms |
104648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2581 ms |
101924 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
