Submission #516108

#	Time	Username	Problem	Language	Result	Execution time	Memory
516108		blue	Teams (CEOI11_tea)	C++17	100 / 100	2116 ms	115048 KiB

tea

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

template <class MyType>
class MySegTree {
public:
  vector<MyType> segtree;

  MySegTree(MyType defaultValue)
  {
    segtree = vector<MyType>(Z<<1, defaultValue);
  }

  void set(int i, MyType v)
  {
    i += Z;
    segtree[i] = v;
    for(i /= 2; i >= 1; i /= 2) segtree[i] = max(segtree[i*2], segtree[(i*2) | 1]);
  }

  MyType query()
  {
    return segtree[1];
  }
};

MySegTree<int> segtree(-INF);
MySegTree<pii> segtree2({-INF, 0});

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


    vi dp(1+n);
    vi dpmx(1+n);

    dp[0] = dpmx[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        if (i - a[i].first >= 0)
            dp[i] = dpmx[i - a[i].first] + 1;
        else
            dp[i] = -INF;
        dpmx[i] = max(dp[i], dpmx[i-1]);

        // cerr << i << " : " << dp[i] << '\n';
    }

    int team_count = dp[n];

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

        // segtree.segtree = vector<int>(Z<<1, -INF);
        segtree = MySegTree(-INF);

        int l = 0;
        int r = -1;

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

        // cerr << "n = " << n << '\n';

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

            if(nl > nr) continue;

            if(nr - nl < 40)
            {
                for(int g = nl; g <= nr; g++)
                    new_dp[i] = max(new_dp[i], new_dp[g]+1);
                continue;
            }

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

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

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

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

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

        if(new_dp[n] == team_count)
            hi = mxs;
        else
            lo = mxs+1;
    }

    // cerr << team_count << ' ' << lo << '\n';







        int mxs = lo;

        // cerr << "\n\n\n\n\n";
        // cerr << lo << ' ' << hi << " : " << mxs << '\n';

        segtree2 = MySegTree(pii{-INF, -1});
        for(int i = 0; i <= n; i++) segtree2.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);

        // cerr << "n = " << n << '\n';

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

            if(nr - nl < 20)
            {
                for(int i2 = nl; i2 <= nr; i2++)
                {
                    if(new_dp[i2]+1 >= new_dp[i])
                    {
                        new_dp[i] = new_dp[i2] + 1;
                        prv[i] = i2;
                    }
                }
                continue;
            }
            // if(i-mxs > i - a[i]) con
            // cerr << "i = " << i << " : " << "nl nr = " << nl << ' ' << nr << '\n';
            if(nl > nr) continue;

            // cerr << "journey " << l << ' ' << r << " -> " << nl << ' ' << nr << '\n';

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

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

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

            while(l < nl)
            {
                segtree2.set(l, {-INF, l});
                l++;
            }
            // cerr << l << ' ' << r << '\n';
            // cerr << "st = " << segtree2[1].first << ' ' << segtree2[1].second << '\n';

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

            // cerr << i << " : " << new_dp[i] << ' ' << prv[i] << '\n';
        }

        vvi teams;
           int I = n;
           while(I != 0)
           {
               teams.push_back(vi(0));
               // cerr << I << ' ' << prv[I] << '\n';
               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;
}

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