oj.uz

Submission #392086

# Submission time Handle Problem Language Result Execution time Memory
392086 2021-04-20T13:09:05 Z nicolaalexandra Teams (CEOI11_tea) C++14
70 / 100
 2500 ms 175156 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47220 KB Output is correct
2 Correct 30 ms 47308 KB Output is correct
3 Correct 30 ms 47292 KB Output is correct
4 Correct 31 ms 47312 KB Output is correct
5 Correct 30 ms 47316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47308 KB Output is correct
2 Correct 30 ms 47300 KB Output is correct
3 Correct 32 ms 47364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47364 KB Output is correct
2 Correct 31 ms 47332 KB Output is correct
3 Correct 30 ms 47392 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47948 KB Output is correct
2 Correct 34 ms 47932 KB Output is correct
3 Correct 34 ms 47948 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 47820 KB Output is correct
2 Correct 35 ms 47972 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 57624 KB Output is correct
2 Correct 82 ms 58308 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 58948 KB Output is correct
2 Correct 77 ms 57668 KB Output is correct
3 Correct 573 ms 59464 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2589 ms 146000 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 2587 ms 175156 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 2587 ms 165272 KB Time limit exceeded
2 Halted 0 ms 0 KB -