Submission #392135

#	Time	Username	Problem	Language	Result	Execution time	Memory
392135		nicolaalexandra	Teams (CEOI11_tea)	C++14	70 / 100	2598 ms	109744 KiB

tea

#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;

pair <int,int> v[DIM],aint[DIM*4];
vector <int> sol[DIM],events[DIM];
vector <pair<int,int> > s;
int t[DIM],dp[DIM];
int n,i,j,k,ans,poz;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = make_pair (-1,st);
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod] = aint[nod<<1];
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod].first = 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);

    if (aint[nod<<1].first > aint[(nod<<1)|1].first)
        aint[nod] = aint[nod<<1];
    else aint[nod] = aint[(nod<<1)|1];
}

void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        if (aint[nod].first > ans)
            ans = aint[nod].first, poz = aint[nod].second;
        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 verif (int lg){
    int i;

    for (i=0;i<=n;i++)
        dp[i] = -1;
    dp[0] = 0;

    build (1,0,n);

    for (i=1;i<=n;i++){
        for (auto it : events[i])
            update (1,0,n,it,dp[it]);

        //if (i < lg)
            //continue;

        ans = -1, poz = 0;
        query (1,0,n,max(0,i-lg),i-1);

        if (ans != -1){
            dp[i] = ans + 1;
            t[i] = poz;
        }
    }

    return dp[n];
}


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

    /// cand incepe sa aiba influenta un dp?
    for (i=1;i<=n;i++)
        events[i + v[i].first - 1].push_back(i-1);

    int maxi = verif (n);

    int st = 1, dr = n, lg;
    while (st <= dr){
        int mid = (st+dr)>>1;

        if (verif(mid) == maxi){ /// incerc o lungime mai mica
            dr = mid-1;
            lg = mid;
        } else st = mid+1;
    }

    verif (lg);

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

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:112:11: warning: 'lg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |     verif (lg);
      |     ~~~~~~^~~~

• 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