Submission #57644

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57644	2018-07-15T16:27:23 Z	Diuven	Teams (CEOI11_tea)	C++11	100 / 100	650 ms	152088 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){
    if(x<0) return pii(-1, -1);
    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);
        if(now.first<0) continue;
        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
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	23800 KB	Output is correct
2	Correct	25 ms	23912 KB	Output is correct
3	Correct	27 ms	23964 KB	Output is correct
4	Correct	28 ms	24184 KB	Output is correct
5	Correct	40 ms	24184 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	24184 KB	Output is correct
2	Correct	21 ms	24184 KB	Output is correct
3	Correct	20 ms	24184 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	24184 KB	Output is correct
2	Correct	24 ms	24184 KB	Output is correct
3	Correct	22 ms	24184 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24280 KB	Output is correct
2	Correct	23 ms	24400 KB	Output is correct
3	Correct	23 ms	24416 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24416 KB	Output is correct
2	Correct	24 ms	24416 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	27784 KB	Output is correct
2	Correct	52 ms	29296 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	29296 KB	Output is correct
2	Correct	50 ms	29440 KB	Output is correct
3	Correct	61 ms	29440 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	72588 KB	Output is correct
2	Correct	399 ms	76508 KB	Output is correct
3	Correct	427 ms	76508 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	531 ms	87528 KB	Output is correct
2	Correct	631 ms	152088 KB	Output is correct
3	Correct	445 ms	152088 KB	Output is correct
4	Correct	452 ms	152088 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	421 ms	152088 KB	Output is correct
2	Correct	309 ms	152088 KB	Output is correct
3	Correct	450 ms	152088 KB	Output is correct
4	Correct	650 ms	152088 KB	Output is correct

Submission #57644

Compilation message