oj.uz

Submission #298210

# Submission time Handle Problem Language Result Execution time Memory
298210 2020-09-12T14:52:08 Z evpipis Teams (CEOI11_tea) C++11
70 / 100
 2500 ms 32144 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;
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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 512 KB Output is correct
2 Correct 23 ms 632 KB Output is correct
3 Correct 28 ms 632 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 640 KB Output is correct
2 Correct 21 ms 512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 4088 KB Output is correct
2 Correct 683 ms 4308 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 4344 KB Output is correct
2 Correct 613 ms 4344 KB Output is correct
3 Correct 747 ms 4856 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2567 ms 28412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2582 ms 32144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2599 ms 30712 KB Time limit exceeded
2 Halted 0 ms 0 KB -