oj.uz

답안 #516074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516074 2022-01-20T11:01:52 Z blue Teams (CEOI11_tea) C++17
100 / 100
 2285 ms 113192 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<int> segtree;
 
void set(int i, int v)
{
    i += Z;
    segtree[i] = v;
    for(i >>= 1; i >= 1; i >>= 1) segtree[i] = max(segtree[i<<1], segtree[(i<<1) | 1]);
}
 
 
vector<pii> segtree2;
void set2(int i, int v)
{
    // cerr << "\n\n" << "set2 " << i << ' ' << v << '\n';
    i += Z;
    segtree2[i].first = v;
    for(i >>= 1; i >= 1; i >>= 1) segtree2[i] = max(segtree2[i<<1], segtree2[(i<<1) | 1]);
    // cerr << "root = " << segtree2[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 dpmx(1+n);
 
    dp[0] = dpmx[0] = 0;
 
    for(int i = 1; i <= n; i++)
    {
        t = -INF;
        if(a[i].first > i)
        {
            ;
        }
        else
        {
            if(i - a[i].first >= 0)
                t = dpmx[i - a[i].first];
        }
 
        dp[i] = max(-INF, t + 1);
        dpmx[i] = max(dp[i], dpmx[i-1]);
 
        // cerr << i << " : " << t << '\n';
    }
 
    int team_count = dp[n];
 
    // int Z = (1<<20);
 
    int z = 0;
    for(int i = 1; i <= n; i++) z = max(z, a[i].first);
 
 
    int lo = 1, hi = n;
    while(lo != hi)
    {
        int mxs = (lo+hi)/2;
 
        segtree = vector<int>(Z<<1, -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 < 30)
            {
                for(int g = nl; g <= nr; g++)
                    new_dp[i] = max(new_dp[i], new_dp[g]+1);
                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]+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 = vector<pii>(Z<<1, {-INF, -1});
        for(int i = 0; i <= n; i++) segtree2[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++;
                set2(r, new_dp[r]);
            }
 
            while(l > nl)
            {
                l--;
                set2(l, new_dp[l]);
            }
 
            while(r > nr)
            {
                set2(r, -INF);
                r--;
            }
 
            while(l < nl)
            {
                set2(l, -INF);
                l++;
            }
            // cerr << l << ' ' << r << '\n';
            // cerr << "st = " << segtree2[1].first << ' ' << segtree2[1].second << '\n';
 
            new_dp[i] = max(-INF, segtree2[1].first+1);
            prv[i] = segtree2[1].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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16608 KB Output is correct
2 Correct 26 ms 33080 KB Output is correct
3 Correct 23 ms 33116 KB Output is correct
4 Correct 24 ms 33336 KB Output is correct
5 Correct 22 ms 33144 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 33124 KB Output is correct
2 Correct 27 ms 33096 KB Output is correct
3 Correct 25 ms 33092 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33184 KB Output is correct
3 Correct 34 ms 33152 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 33164 KB Output is correct
2 Correct 35 ms 33164 KB Output is correct
3 Correct 42 ms 33176 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 33216 KB Output is correct
2 Correct 35 ms 33208 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 34840 KB Output is correct
2 Correct 178 ms 34792 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 35020 KB Output is correct
2 Correct 136 ms 34668 KB Output is correct
3 Correct 177 ms 35124 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1646 ms 51308 KB Output is correct
2 Correct 1284 ms 52888 KB Output is correct
3 Correct 1612 ms 52068 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2139 ms 59900 KB Output is correct
2 Correct 2024 ms 113192 KB Output is correct
3 Correct 1819 ms 62164 KB Output is correct
4 Correct 2069 ms 55696 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1245 ms 62332 KB Output is correct
2 Correct 265 ms 63312 KB Output is correct
3 Correct 2285 ms 60024 KB Output is correct
4 Correct 2242 ms 59624 KB Output is correct