Submission #463757

#	Time	Username	Problem	Language	Result	Execution time	Memory
463757		idk321	Global Warming (CEOI18_glo)	C++17	100 / 100	869 ms	37684 KiB

glo

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

const int MIN = -2000000001;
const int MAX = 2000000001;

int n, x;
const int N = 200005;
int tree[4 * N][2];

int getMax(int from, int to, int a, int b, int node, int treeNum) {
    if (from > to) return 0;
    if (from <= a && b <= to) return tree[node][treeNum];

    int mid = (a + b) / 2;
    int res = -1;
    if (from <= mid) res = max(res, getMax(from, to, a, mid, node * 2, treeNum));
    if (to > mid) res = max(res, getMax(from, to, mid +1, b, node * 2 + 1, treeNum));

    return res;
}

void insertMax(int i, int num, int a, int b, int node, int treeNum) {
    if (a == b) {
        tree[node][treeNum] = max(tree[node][treeNum], num);
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) insertMax(i, num, a, mid, node * 2, treeNum);
    else insertMax(i, num, mid + 1, b, node * 2 + 1, treeNum);
    tree[node][treeNum] = max(tree[node * 2][treeNum], tree[node * 2 + 1][treeNum]);
}

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

    cin >> n >> x;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    vector<int> left(n);

    set<int> all;
    map<int, int> mapTo;
    for (int i = 0; i < n; i++) all.insert(v[i]);
    int cur = 0;
    for (int i : all) {
        mapTo[i] = cur;
        cur++;
    }

    vector<int> getsTo(n);
    vector<int> org(v.begin(), v.end());
    set<array<int, 2>> orgAndNew;
    for (int i = 0; i < n; i++) {
        v[i] = mapTo[v[i]];
        orgAndNew.insert({org[i], v[i]});
    }

    for (int i = 0; i < n; i++) {
        auto it = orgAndNew.upper_bound({org[i] + x, -1});
        if (it == orgAndNew.begin()) {
            getsTo[v[i]] = -1;
        } else {
            it--;
            getsTo[v[i]] = (*it)[1];
        }
    }

    for (int i = 0; i < n; i++) {
        insertMax(v[i], 1 + getMax(0, getsTo[v[i]], 0, N - 1, 1, 0), 0, N - 1, 1, 1);
        insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 0), 0, N - 1, 1, 0);
        insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 1), 0, N - 1, 1, 1);
    }

    cout << getMax(0, N - 1, 0, N - 1, 1, 1) << "\n";
}

/*
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