Submission #57644

#	Time	Username	Problem	Language	Result	Execution time	Memory
57644		Diuven	Teams (CEOI11_tea)	C++11	100 / 100	650 ms	152088 KiB

tea

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10