oj.uz

Submission #392135

# Submission time Handle Problem Language Result Execution time Memory
392135 2021-04-20T14:38:27 Z nicolaalexandra Teams (CEOI11_tea) C++14
70 / 100
 2500 ms 109744 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47180 KB Output is correct
2 Correct 30 ms 47304 KB Output is correct
3 Correct 29 ms 47196 KB Output is correct
4 Correct 29 ms 47232 KB Output is correct
5 Correct 30 ms 47296 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47192 KB Output is correct
2 Correct 31 ms 47248 KB Output is correct
3 Correct 31 ms 47180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47304 KB Output is correct
2 Correct 31 ms 47216 KB Output is correct
3 Correct 32 ms 47296 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47656 KB Output is correct
2 Correct 51 ms 47624 KB Output is correct
3 Correct 50 ms 47684 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 47512 KB Output is correct
2 Correct 50 ms 47664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 53796 KB Output is correct
2 Correct 527 ms 54200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 54340 KB Output is correct
2 Correct 463 ms 53704 KB Output is correct
3 Correct 589 ms 54724 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2593 ms 98824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2585 ms 109744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2598 ms 105800 KB Time limit exceeded
2 Halted 0 ms 0 KB -