Submission #392086

#	Time	Username	Problem	Language	Result	Execution time	Memory
392086		nicolaalexandra	Teams (CEOI11_tea)	C++14	70 / 100	2589 ms	175156 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],p[DIM],rmq[30][DIM];
int n,i,j,k,maxim;

int get_max (int x, int y){
    int nr = p[y-x+1];
    return max (rmq[nr][x],rmq[nr][y-(1<<nr)+1]);
}

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);

    for (i=1;i<=n;i++)
        rmq[0][i] = v[i].first;

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= n && rmq[i-1][j + (1<<(i-1))] > rmq[i][j])
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=n;i++)
        p[i] = p[i/2] + 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++){
        int st = i, dr = n, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (v[i].first <= mid-i+1){
                sol = mid;
                dr = mid-1;
            } else st = mid+1;
        }

        events[sol].push_back(i-1);
    }

    int maxim = -1;
    for (i=1;i<=n;i++){

        for (auto it : events[i]){
            if (dp[it].first > maxim){
                maxim = dp[it].first;
                s.clear();
                s.push_back(make_pair(dp[it].second,it));
            } else {
                if (dp[it].first == maxim)
                    s.push_back(make_pair(dp[it].second,it));
            }
        }

        if (maxim == -1)
            continue;

        /// calculez dp[i];
        dp[i].first = maxim + 1;
        for (auto it : s){
            if (max(it.first,i-it.second) < dp[i].second){
                dp[i].second = max(it.first,i-it.second);
                t[i] = it.second;
            }
        }
    }

    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: 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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10