Submission #392120

#	Time	Username	Problem	Language	Result	Execution time	Memory
392120		nicolaalexandra	Teams (CEOI11_tea)	C++14	0 / 100	2581 ms	104648 KiB

tea

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10