Submission #298232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
298232	2020-09-12T15:53:40 Z	evpipis	Teams (CEOI11_tea)	C++11	100 / 100	1801 ms	204944 KB

#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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	149112 KB	Output is correct
2	Correct	119 ms	148984 KB	Output is correct
3	Correct	115 ms	148988 KB	Output is correct
4	Correct	113 ms	148984 KB	Output is correct
5	Correct	113 ms	149112 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	111 ms	149112 KB	Output is correct
2	Correct	111 ms	148984 KB	Output is correct
3	Correct	120 ms	149112 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	149112 KB	Output is correct
2	Correct	112 ms	149112 KB	Output is correct
3	Correct	111 ms	149112 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	118 ms	149256 KB	Output is correct
2	Correct	122 ms	149240 KB	Output is correct
3	Correct	121 ms	149368 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	149260 KB	Output is correct
2	Correct	119 ms	149368 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	212 ms	152596 KB	Output is correct
2	Correct	227 ms	153208 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	231 ms	153336 KB	Output is correct
2	Correct	214 ms	153080 KB	Output is correct
3	Correct	234 ms	153336 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1312 ms	187220 KB	Output is correct
2	Correct	1279 ms	188920 KB	Output is correct
3	Correct	1266 ms	186616 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1693 ms	194108 KB	Output is correct
2	Correct	1661 ms	203128 KB	Output is correct
3	Correct	1713 ms	202216 KB	Output is correct
4	Correct	1559 ms	197916 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1020 ms	184068 KB	Output is correct
2	Correct	415 ms	171640 KB	Output is correct
3	Correct	1731 ms	203028 KB	Output is correct
4	Correct	1801 ms	204944 KB	Output is correct