Submission #1261861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261861		ankite	Global Warming (CEOI18_glo)	C++20	62 / 100	241 ms	15600 KiB

glo

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

int n, x, a[200200];

vector<int> vals;
unordered_map<int, int> f;
void compress() {
    for (int i=1; i<=n; i++) vals.push_back(a[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i=0; i<vals.size(); i++) f[vals[i]] = i + 1;
}

int seg[800800];
#define mid (l + ((r - l ) >> 1))
#define left (id << 1)
#define right (id << 1 | 1)
const int inf = 2e9;
void update(int pos, int val, int id = 1, int l = 1, int r = n) {
    if (l == r) { if (l == pos) seg[id] = val; return; }
    if (pos <= mid) update(pos, val, left, l, mid);
    else update(pos, val, right, mid + 1, r);
    seg[id] = max(seg[left], seg[right]);
}

int get(int lo, int hi, int id = 1, int l = 1, int r = n) {
    if (lo > hi) return 0;
    if (r < lo  ||  l > hi) return 0;
    if (lo <= l  &&  r <= hi) return seg[id];
    return max(get(lo, hi, left, l, mid), get(lo, hi, right, mid + 1, r));
}

int pre[200200], preval[200200];

signed main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> x;
    for (int i=1; i<=n; i++) cin >> a[i];

    compress();

    preval[0] = inf;
    for (int i=1; i<=n; i++) {
        int cur_best = 1 + get(1, f[a[i]] - 1);
        if (cur_best >= pre[i-1]) {
            if (cur_best > pre[i-1]) {
                pre[i] = cur_best;
                preval[i] = a[i];
            } else {
                pre[i] = cur_best;
                preval[i] = min(a[i], preval[i-1]);
            }
        } else {
            pre[i] = pre[i-1];
            preval[i] = preval[i-1];
        }

        update(f[a[i]], cur_best);
    }


    fill(seg, seg + (4 * n) + 10, 0);

    int ans = 0;
    for (int i=n; i; i--) {
        int idx = upper_bound(vals.begin(), vals.end(), preval[i] - x) - vals.begin() + 1;

        int rightside = get(idx, vals.size());
        int cur_best = pre[i] + rightside;
        ans = max(ans, cur_best);
        update(f[a[i]], 1 + get(f[a[i]] + 1, n));
    }

    cout << ans;

    return 0;
}

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