Submission #515954

#	Time	Username	Problem	Language	Result	Execution time	Memory
515954		apostoldaniel854	Teams (CEOI11_tea)	C++14	70 / 100	2542 ms	53196 KiB

tea

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6;

struct node_info {
    int mx, id;
    node_info(int value = 0, int id = 0) {
        this->mx = value;
        this->id = id;
    }
    node_info operator + (node_info other) const {
        node_info RES;
        if (mx > other.mx)
            RES = {this->mx, this->id};
        else
            RES = other;
        return RES;
    }
};

class SegTree {
private:
    vector <node_info> seg;
public:
    SegTree(int n) {
        seg.resize(1 + 4 * n);
    }
    void update_pos(int node, int lb, int rb, int pos, node_info val) {
        if (lb == rb) {
            seg[node] = val;
            return;
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (pos <= mid)
            update_pos(lnode, lb, mid, pos, val);
        else
            update_pos(rnode, mid + 1, rb, pos, val);
        seg[node] = seg[lnode] + seg[rnode];
    }
    node_info query_range(int node, int lb, int rb, int ql, int qr) {
        if (lb == ql && rb == qr)
            return seg[node];
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (ql <= mid && qr <= mid)
            return query_range(lnode, lb, mid, ql, qr);
        else if (mid + 1 <= ql && mid + 1 <= qr)
            return query_range(rnode, mid + 1, rb, ql, qr);
        else
            return query_range(lnode, lb, mid, ql, mid) + query_range(rnode, mid + 1, rb, mid + 1, qr);
    }
};

pair <int, int> a[1 + MAX_N];
int dp[1 + MAX_N];
int from[1 + MAX_N];

int n;


int get_max_teams(int limit_size) {
    SegTree D(n);
    dp[0] = 0;
    from[0] = 0;
    D.update_pos(1, 0, n, 0, node_info(dp[0], 0));
    for (int i = 1; i <= n; i++) {
        if (max(0, i - limit_size) <= i - a[i].first) {
            node_info res = D.query_range(1, 0, n, max(0, i - limit_size), i - a[i].first);
            dp[i] = res.mx + 1;
            from[i] = res.id;
        }
        else {
            dp[i] = -(1 << 30);
            from[i] = -1;
        }
        D.update_pos(1, 0, n, i, node_info(dp[i], i));
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + n + 1);
    int max_teams = get_max_teams(n);
    int lb = 1, rb = n, min_size = n;
    while (lb <= rb) {
        int mid = (lb + rb) / 2;
        if (get_max_teams(mid) == max_teams)
            min_size = mid, rb = mid - 1;
        else
            lb = mid + 1;
    }
    get_max_teams(min_size);
    cout << max_teams << "\n";
    int curr = n;
    while (curr > 0) {
        cout << curr - from[curr] << " ";
        for (int i = curr; i > from[curr]; i--)
            cout << a[i].second << " ";
        cout << "\n";
        curr = from[curr];
    }
    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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10