Submission #1193932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193932		anmattroi	Global Warming (CEOI18_glo)	C++17	100 / 100	173 ms	4352 KiB

glo

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

int n, x;
int a[maxn], b[maxn], n1 = 0, f[maxn], g[maxn];

int bit[maxn];

void upd(int u, int d, bool rev) {
    if (!rev) for (int i = u; i <= n1; i += i & -i) bit[i] = max(bit[i], d);
    else for (int i = u; i > 0; i -= i & -i) bit[i] = max(bit[i], d);
}

int get(int u, bool rev) {
    int ans = 0;

    if (!rev) for (int i = u; i > 0; i -= i & -i) ans = max(ans, bit[i]);
    else for (int i = u; i <= n1; i += i & -i) ans = max(ans, bit[i]);

    return ans;
}

void rs() {
    for (int i = 1; i <= n1; i++) bit[i] = 0;
}

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

    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[++n1] = a[i];
    }
    sort(b + 1, b + n1 + 1);
    n1 = unique(b + 1, b + n1 + 1) - b - 1;

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int p = lower_bound(b + 1, b + n1 + 1, a[i]) - b;
        f[i] = get(p-1, 0) + 1;
        upd(p, f[i], 0);
    }
    rs();
    for (int i = n; i >= 1; i--) {
        int p = lower_bound(b + 1, b + n1 + 1, a[i]) - b;
        g[i] = get(p+1, 1) + 1;
        upd(p, g[i], 1);
    }
    rs();
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(b + 1, b + n1 + 1, a[i]+x) - b - 1;
        ans = max(ans, get(p, 0) + g[i]);
        p = lower_bound(b + 1, b + n1 + 1, a[i]) - b;
        upd(p, f[i], 0);
    }
    rs();
    for (int i = n; i >= 1; i--) {
        int p = upper_bound(b + 1, b + n1 + 1, a[i]-x) - b;
        ans = max(ans, get(p, 1) + f[i]);
        p = lower_bound(b + 1, b + n1 + 1, a[i]) - b;
        upd(p, g[i], 1);
    }
    cout << ans;
}
/*
8 10
7 3 5 12 2 7 3 4
*/

• 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