Submission #1264281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264281		MinhKien	Global Warming (CEOI18_glo)	C++20	100 / 100	109 ms	5816 KiB

glo

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 2e5 + 10;
const int INF = 2e9;

int n, x, a[N], RES;
int mxlen, v[N];
int pre[N], suf[N];
vector <int> vals;

int FindSmall(int val) {
    int l = 0, r = mxlen, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;

        if (v[m] < val) {
            l = m + 1;
            ans = m;
        } else {
            r = m - 1;
        }
    }

    ++ans;
    v[ans] = val;
    mxlen = max(mxlen, ans);
    return ans;
}

int FindLarge(int val) {
    int l = 0, r = mxlen, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;

        if (v[m] > val) {
            l = m + 1;
            ans = m;
        } else {
            r = m - 1;
        }
    }

    ++ans;
    v[ans] = val;
    mxlen = max(mxlen, ans);
    return ans;
}

int id(int p) {
    return lower_bound(vals.begin(), vals.end(), p) - vals.begin();
}

struct BIT {
    int b[N << 1];

    void clear() {
        for (int i = 1; i <= vals.size(); ++i) b[i] = 0;
    }

    void update(int u, int val) {
        while (u <= vals.size()) {
            b[u] = max(b[u], val);
            u += u & -u;
        }
    }

    int get(int u) {
        int res = 0;
        while (u > 0) {
            res = max(res, b[u]);
            u -= u & -u;
        }
        return res;
    }
} bit;

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> x;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        vals.push_back(a[i]);
        vals.push_back(a[i] - x);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    v[0] = -INF;
    for (int i = 1; i <= n; ++i) {
        pre[i] = FindSmall(a[i]);
    }
    RES = mxlen;

    v[0] = INF;
    mxlen = 0;
    for (int i = n; i >= 1; --i) {
        suf[i] = FindLarge(a[i]);
    }

    bit.update(id(a[1] - x) + 1, pre[1]);
    for (int i = 2; i <= n; ++i) {
        RES = max(RES, bit.get(id(a[i])) + suf[i]);
        bit.update(id(a[i] - x) + 1, pre[i]);
    }

    cout << RES << "\n";

    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