Submission #1276188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276188		nanaseyuzuki	Global Warming (CEOI18_glo)	C++20	0 / 100	105 ms	5268 KiB

glo

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

#define ll long long
#define all(a) a.begin(), a.end()

const int MN = 200005;

// Fenwick Tree (BIT) cho max
struct BIT {
    int n;
    vector<int> bit;
    BIT(int _n = 0) { init(_n); }
    void init(int _n) { n = _n; bit.assign(n + 1, 0); }

    void update(int i, int val) {
        for (; i <= n; i += i & -i)
            bit[i] = max(bit[i], val);
    }

    int query(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i)
            res = max(res, bit[i]);
        return res;
    }
};

int n, x, a[MN], lis[MN], suf[MN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> x;
    vector<int> comp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        comp.push_back(a[i]);
    }
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    int m = comp.size();
    BIT bit1(m);
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(all(comp), a[i]) - comp.begin() + 1;
        lis[i] = bit1.query(id - 1) + 1;
        bit1.update(id, lis[i]);
    }
    BIT bit2(m);
    for (int i = n; i >= 1; i--) {
        int id = m - (lower_bound(all(comp), a[i]) - comp.begin()) + 1;
        suf[i] = bit2.query(id - 1) + 1;
        bit2.update(id, suf[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, lis[i]);
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound(all(comp), a[i] - x) - comp.begin();
        if (pos < 1) continue;
        int j = bit2.query(m - pos + 1);
        res = max(res, lis[i] + j);
    }
    cout << res << '\n';
    return 0;
}

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