oj.uz

Submission #512059

# Submission time Handle Problem Language Result Execution time Memory
512059 2022-01-16T06:24:58 Z blue Teams (CEOI11_tea) C++17
0 / 100
 2500 ms 88784 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

const int INF = 100'000'000;

const int Z = (1<<20);
vector<pii> segtree;

void set(int i, int v)
{
    i += Z;
    segtree[i].first = v;
    for(i >>= 1; i >= 1; i >>= 1) segtree[i] = max(segtree[i<<1], segtree[(i<<1) | 1]);
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    pii a[1+n];
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1, a+n+1);

    int t;

    vi dp(1+n);

    vi occ[1+n];

    vi bit(1+n+1, -INF);
    // bit[0 +1] = 0;
    for(int j = 0 +1; j <= n +1; j += j&-j) bit[j] = 0;

    occ[0].push_back(0);

    for(int i = 1; i <= n; i++)
    {
        t = -INF;
        if(a[i].first > i)
        {
            ;
        }
        else
        {
            for(int j = i - a[i].first +1; j >= 0 +1; j -= j&-j)
                t = max(t, bit[j]+1);

            // cerr << i << " -> " << i - a[i].first << '\n';

            for(int j = i +1; j <= n +1; j += j&-j)
                bit[j] = max(bit[j], t);
        }

        dp[i] = t;
        if(t != -INF) occ[dp[i]].push_back(i);

        // cerr << i << " : " << t << '\n';
    }

    int team_count = dp[n];

    // int Z = (1<<20);


    int lo = 1, hi = n;
    while(1)
    {
        int mxs = (lo+hi)/2 + 1;

        segtree = vector<pii>(Z<<1, {-INF, -1});
        for(int i = 0; i <= n; i++) segtree[Z+i].second = i;

        int l = 0;
        int r = -1;

        vi new_dp(1+n, -INF);
        new_dp[0] = 0;

        vi prv(1+n, -1);

        for(int i = 1; i <= n; i++)
        {
            int nl = max(0, i-mxs);
            int nr = max(-1, i - a[i].first);
            // if(i-mxs > i - a[i]) con
            if(nl > nr) continue;

            while(r < nr)
            {
                r++;
                set(r, new_dp[r]);
            }

            while(l > nl)
            {
                l--;
                set(l, new_dp[l]);
            }

            while(r > nr)
            {
                set(r, -INF);
                r--;
            }

            while(l < nl)
            {
                set(l, -INF);
                l++;
            }

            new_dp[i] = max(-INF, segtree[1].first+1);
            prv[i] = segtree[1].second;
        }

        if(lo == hi)
        {
            vvi teams;
            int I = n;
            while(I != 0)
            {
                teams.push_back(vi(0));
                for(int q = I; q > prv[I]; q--)
                    teams.back().push_back(a[q].second);
                I = prv[I];
            }

            cout << team_count << '\n';
            for(int f = 0; f < team_count; f++)
            {
                cout << sz(teams[f]) << ' ';
                for(int w: teams[f]) cout << w << ' ';
                cout << '\n';
            }
            return 0;
        }
        else
        {
            if(new_dp[n] == team_count)
                lo = mxs;
            else
                hi = mxs-1;
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16712 KB Output is correct
2 Correct 37 ms 33184 KB Output is correct
3 Incorrect 38 ms 33140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 33100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 33092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 33400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 33424 KB Output is correct
2 Incorrect 65 ms 33364 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 37496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 38088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1906 ms 74616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1633 ms 88784 KB Output isn't correct
2 Halted 0 ms 0 KB -