oj.uz

답안 #298232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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