oj.uz

Submission #57642

# Submission time Handle Problem Language Result Execution time Memory
57642 2018-07-15T16:15:53 Z Diuven Teams (CEOI11_tea) C++11
0 / 100
 572 ms 86872 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=1000010, inf=2e9;

struct stu {
    int a, idx, cut;
} A[MX];

int n;
int D[MX];

pii tree[MX];
vector<int> P[MX];

void upt(int x, int idx){
    pii p=pii(D[idx], idx);
    for(; 0<x && x<=n; x+=x&(-x)) tree[x]=max(tree[x], p);
}
pii mx(int x){
    pii res=pii(0,0);
    for(; 0<x; x-=x&(-x)) res=max(res, tree[x]);
    return res;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>A[i].a, A[i].idx=i;
    sort(A+1, A+n+1, [](stu &a, stu &b){ return a.a<b.a; });

    for(int i=1; i<=n; i++){
        for(int x:P[i]) upt(x, x);
        pii now=mx(i-A[i].a);
        A[i].cut=now.second;
        D[i]=now.first+1;
        int m=i-now.second;
        P[min(n+1, i+m)].push_back(i);
    }

    vector<vector<int>> ans;

    int now=n;
    while(now>0){
        vector<int> put;
        for(int i=now; i>A[now].cut; i--)
            put.push_back(A[i].idx);
        ans.push_back(put);
        now=A[now].cut;
    }
    
    cout<<ans.size()<<'\n';
    for(vector<int> &V:ans){
        cout<<V.size()<<' ';
        for(int x:V) cout<<x<<' ';
        cout<<'\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23800 KB Output is correct
2 Incorrect 23 ms 23908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 23944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 23944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 24324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 28356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 29552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 420 ms 72676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 572 ms 86872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 487 ms 86872 KB Output isn't correct
2 Halted 0 ms 0 KB -