Submission #1264737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264737		nguyenphucanhkhoi	Global Warming (CEOI18_glo)	C++20	0 / 100	171 ms	5804 KiB

glo

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

#define ll long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define hash vector<int>
#define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
#define REV(i, n) for (int i = (n); i >= 1; i--)
#define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
#define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
#define MASK(k) (1 << (k))
#define BIT(i, n) (((n) >> ((i) - 1)) & 1)
#define OFF(i, n) ((n) & ~MASK((i) - 1))
#define ON(i, n) ((n) | MASK((i) - 1))
#define NUM_BIT(n) (__builtin_popcount(n))

const int MAXN = 4e5 + 26;
int n, x, res, a[MAXN], b[MAXN], bit[MAXN], L[MAXN], R[MAXN];

void upd(int u, int v) {
    for (; u <= 2 * n; u += u & (-u)) bit[u] = max(bit[u], v);
}

int get(int u) {
    if (u <= 0) return 0;
    int ans = 0;
    for (; u; u -= u & (-u)) ans = max(ans, bit[u]);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> x;
    REP(i, n) cin >> a[i], b[2 * i - 1] = a[i], b[2 * i] = a[i] - x;
    sort(b + 1, b + 2 * n + 1);
    REP(i, n) {
        int id = lower_bound(b + 1, b + 2 * n + 1, a[i]) - b - 1;
        L[i] = get(id) + 1;
        id = lower_bound(b + 1, b + 2 * n + 1, a[i]) - b;
        upd(id, L[i]);
    }
    REP(i, 2 * n) bit[i] = 0;
    REV(i, n) {
        int tmp = lower_bound(b + 1, b + 2 * n + 1, a[i] - x) - b;
        int id = 2 * n - tmp;
        res = max(res, L[i] + get(id));
        tmp = lower_bound(b + 1, b + 2 * n + 1, a[i]) - b - 1;
        id = 2 * n - tmp + 1;
        R[i] = get(id) + 1;
        tmp = lower_bound(b + 1, b + 2 * n + 1, a[i]) - b;
        id = 2 * n - tmp + 1;
        upd(id, R[i]);
    }
    cout << res;
    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