Submission #636995

#	Time	Username	Problem	Language	Result	Execution time	Memory
636995		tvladm2009	Global Warming (CEOI18_glo)	C++14	100 / 100	274 ms	7728 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2 * 1e5;
int a[MAX_N + 1], dp1[MAX_N + 1], dp2[MAX_N + 1], ind[MAX_N + 1];
pair<int, int> v[MAX_N + 1];
int n, x;

class BIT {
    int aib[MAX_N + 1];

    void update(int p, int val) {
        for (int i = p; i >= 1; i -= i & -i) {
            aib[i] = max(aib[i], val);
        }
    }

    int query(int p) {
        int ans = 0;
        for (int i = p; i <= n; i += i & -i) {
            ans = max(ans, aib[i]);
        }
        return ans;
    }

public:
    void reset() {
        memset(aib, 0, sizeof(aib));
    }

    void update_greater(int x, int val) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v;
        update(p, val);
    }

    int query_greater(int x) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x + 1, 0)) - v;
        return query(p);
    }

    void update_smaller(int x, int val) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v;
        update(n - p + 1, val);
    }

    int query_smaller(int x) {
        int p = lower_bound(v + 1, v + n + 1, make_pair(x, 0)) - v - 1;
        return query(n - p + 1);
    }
} aib;

void norm() {
    for (int i = 1; i <= n; i++) {
        v[i] = {a[i], i};
    }
    sort(v + 1, v + n + 1);
    int cnt = 1;
    ind[v[1].second] = cnt;
    for (int i = 2; i <= n; i++) {
        if (v[i].first != v[i - 1].second) {
            cnt++;
        }
        ind[v[i].second] = cnt;
    }
}

void solve() {
    aib.reset();
    for (int i = n; i >= 1; i--) {
        dp2[i] = aib.query_greater(a[i]) + 1;
        aib.update_greater(a[i], dp2[i]);
    }
    int ans = 0;
    aib.reset();
    for (int i = 1; i <= n; i++) {
        int cur = aib.query_smaller(a[i] + x) + dp2[i];
        ans = max(ans, cur);
        dp1[i] = aib.query_smaller(a[i]) + 1;
        aib.update_smaller(a[i], dp1[i]);
    }
    cout << ans << "\n";
}

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    norm();
    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