제출 #1243846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243846		wedonttalkanymore	Global Warming (CEOI18_glo)	C++20	100 / 100	288 ms	131600 KiB

glo

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

int dp[N][2];
int n, x;
int a[N];

struct ST {
    struct item {
        pii val;
        item *left = nullptr;
        item *right = nullptr;
    };
    item *root = nullptr;
    int L, R;
    ST(int l, int r) {
        L = l, R = r;
        root = new item();
    }
    void update(item *&i, int l, int r, int pos, pii val) {
        if (!i) i = new item();
        if (l == r) {
            i->val.fi = max(i->val.fi, val.fi);
            i->val.se = max(i->val.se, val.se);
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(i->left, l, mid, pos, val);
        else update(i->right, mid + 1, r, pos, val);
        pii left_val = i->left ? i->left->val : make_pair(0LL, 0LL);
        pii right_val = i->right ? i->right->val : make_pair(0LL, 0LL);
        i->val.fi = max(left_val.fi, right_val.fi);
        i->val.se = max(left_val.se, right_val.se);
    }
    pii get(item *i, int l, int r, int u, int v) {
        if (u > r || v < l || !i) return make_pair(0, 0);
        if (u <= l && r <= v) return i->val;
        int mid = (l + r) / 2;
        pii res;
        pii L = get(i->left, l, mid, u, v);
        pii R = get(i->right, mid + 1, r, u, v);
        res.fi = max(L.fi, R.fi);
        res.se = max(L.se, R.se);
        return res;
    }
    void update(int pos, pii val) {
        update(root, L, R, pos, val);
    }
    pii get(int l, int r) {
        return get(root, L, R, l, r);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ST st(0, 1e12);
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 1;
        // for (int j = 1; j < i; j++) {
        //     if (a[j] < a[i]) {
        //         dp[i][0] = max(dp[i][0], dp[j][0] + 1);
        //         dp[i][1] = max(dp[i][1], dp[j][1] + 1);
        //     }
        // }
        auto tmp = st.get(0, a[i] - 1);
        dp[i][0] = max(dp[i][0], tmp.fi + 1);
        dp[i][1] = max(dp[i][1], tmp.se + 1);
        int Left = max(0LL, a[i] - x - 1);
        int Right = a[i] + x - 1;
        // for (int j = 1; j < i; j++) {
        //     if (Left <= a[j] && a[j] <= Right) {
        //         dp[i][1] = max(dp[i][1], dp[j][0] + 1);
        //     }
        // }
        tmp = st.get(Left, Right);
        dp[i][1] = max(dp[i][1], tmp.fi + 1);
        st.update(a[i], make_pair(dp[i][0], dp[i][1]));
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 1; j++) ans = max(ans, dp[i][j]);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25