Submission #1272043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272043		pvb.tunglam	Global Warming (CEOI18_glo)	C++20	100 / 100	81 ms	3548 KiB

glo

#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_

using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll oo = 8e18;

/*----------- I alone decide my fate! ----------*/
/*   Fenwick tree for range maximum queries    */

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n): n(n), bit(n+1, 0) {}
    void update(int x, int val) {
        for (; x <= n; x += x & -x)
            bit[x] = max(bit[x], val);
    }
    int query(int x) {
        int res = 0;
        for (; x > 0; x -= x & -x)
            res = max(res, bit[x]);
        return res;
    }
};

int N, d;
int a[200009];

void solve() {
    cin >> N >> d;
    for (int i = 1; i <= N; i++) cin >> a[i];

    // coordinate compression
    vector<int> vals(a+1, a+N+1);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_id = [&](int x) {
        return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
    };

    int M = vals.size();
    Fenwick bit0(M), bit1(M);

    int res = 0;
    for (int i = 1; i <= N; i++) {
        int id = get_id(a[i]);

        // dp[i][0] = 1 + max(dp[j][0]) with a[j] < a[i]
        int best0 = bit0.query(id-1) + 1;

        // dp[i][1] from two cases:
        int best1 = bit1.query(id-1) + 1; // continue in state1 with smaller a[j]

        // also can jump from state0 with condition a[j] ≤ a[i] + d - 1
        int lim = a[i] + d - 1;
        int lim_id = upper_bound(vals.begin(), vals.end(), lim) - vals.begin(); 
        if (lim_id > 0) {
            best1 = max(best1, bit0.query(lim_id) + 1);
        }

        res = max({res, best0, best1});
        bit0.update(id, best0);
        bit1.update(id, best1);
    }

    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
    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