Submission #298232

#	Time	Username	Problem	Language	Result	Execution time	Memory
298232		evpipis	Teams (CEOI11_tea)	C++11	100 / 100	1801 ms	204944 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;
vector<int> rec[2*len];

struct val{
    int num, sz;

    val(int a = -inf, int b = inf){
        num = a;
        sz = b;
    }

    bool operator > (const val &other) const{
        if (num > other.num) return true;
        if (num < other.num) return false;
        return (sz < other.sz);
    }

    bool operator < (const val &other) const{
        if (num > other.num) return false;
        if (num < other.num) return true;
        return !(sz < other.sz);
    }
};

int opt[len], n;
val dp[len];
ii arr[len];

struct seg_tree{
    pair<val, int> tree[4*len];

    seg_tree(){
        for (int i = 0; i < 4*len; i++)
            tree[i] = mp(val(), 0);
    }

    void upd(int p, int l, int r, int i, val 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]);
    }

    pair<val, int> ask(int p, int l, int r, int i, int j){
        if (r < i || j < l)
            return mp(val(), 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));
    }
};

seg_tree seg1, seg2;

bool comp(int a, int b){
    return (a-arr[a].fi < b-arr[b].fi);
}

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

    dp[0] = val(0, 1);
    seg2.upd(1, 0, n, 0, dp[0]);
    rec[0+dp[0].sz].pb(0);

    for (int i = 1; i <= n; i++){
        for (auto j: rec[i]){
            seg2.upd(1, 0, n, j, val());
            seg1.upd(1, 0, n, j, val(dp[j].num, -j));
        }

        dp[i] = val();
        pair<val, int> case1 = seg1.ask(1, 0, n, 0, i-arr[i].fi);
        pair<val, int> case2 = seg2.ask(1, 0, n, 0, i-arr[i].fi);

        if (case2.fi > dp[i])
            dp[i] = case2.fi, opt[i] = case2.se;

        case1.fi.sz += i;
        if (case1.fi > dp[i])
            dp[i] = case1.fi, opt[i] = case1.se;

        if (dp[i] > val()){
            dp[i].num++;
            seg2.upd(1, 0, n, i, dp[i]);
            rec[i+dp[i].sz].pb(i);
        }
    }

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

    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:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tea.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10