Submission #298210

#	Time	Username	Problem	Language	Result	Execution time	Memory
298210		evpipis	Teams (CEOI11_tea)	C++11	70 / 100	2599 ms	32144 KiB

tea

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e6+5, inf = 1e9;
int opt[len], dp[len], n;
ii arr[len], tree[4*len];

void upd(int p, int l, int r, int i, int v){
    if (l == r)
        return void(tree[p] = mp(v, i));

    int mid = (l+r)/2;
    if (i <= mid)
        upd(2*p, l, mid, i, v);
    else
        upd(2*p+1, mid+1, r, i, v);
    tree[p] = max(tree[2*p], tree[2*p+1]);
}

ii ask(int p, int l, int r, int i, int j){
    if (r < i || j < l) return mp(-inf, 0);
    if (i <= l && r <= j) return tree[p];

    int mid = (l+r)/2;
    return max(ask(2*p, l, mid, i, j), ask(2*p+1, mid+1, r, i, j));
}

int split(int k){
    for (int i = 1; i <= n; i++){
        ii temp = ask(1, 0, n, max(0, i-k), i-arr[i].fi);
        if (temp.fi == -inf)
            dp[i] = -inf;
        else
            dp[i] = temp.fi+1, opt[i] = temp.se;

        upd(1, 0, n, i, dp[i]);
    }

    return dp[n];
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i].fi), arr[i].se = i;

    sort(arr+1, arr+1+n);

    int best = split(n), l = 1, r = n;
    while (l < r){
        int mid = (l+r)/2;
        if (split(mid) == best)
            r = mid;
        else
            l = mid+1;
    }

    split(l);

    printf("%d\n", dp[n]);

    int i = n;
    while (i > 0){
        int j = opt[i];
        printf("%d", i-j);
        while (i > j){
            printf(" %d", arr[i].se);
            i--;
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

tea.cpp: In function 'int main()':
tea.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d", &arr[i].fi), arr[i].se = i;
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• 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