Submission #636993

#	Time	Username	Problem	Language	Result	Execution time	Memory
636993		tvladm2009	Global Warming (CEOI18_glo)	C++14	0 / 100	251 ms	12728 KiB

glo

#include <bits/stdc++.h>
#define int long long

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];
int aib1[MAX_N + 1], aib2[MAX_N + 1];
pair<int, int> v[MAX_N + 1];
int n, x;

int cb(int val) {
    int l = 1, r = n, sol = -1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (v[mid].first <= val) {
            sol = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ind[v[sol].second];
}

void update1(int x, int val) {
    x = cb(x);
    if (x == 0) {
        return;
    }
    for (int i = x; i <= n; i += i & -i) {
        aib1[i] = max(aib1[i], val);
    }
}

void update2(int x, int val) {
    x = cb(x);
    if (x == 0) {
        return;
    }
    for (int i = x; i >= 1; i -= i & -i) {
        aib2[i] = max(aib2[i], val);
    }
}

int query1(int x) {
    x = cb(x);
    if (x == 0) {
        return 0;
    }
    int ans = 0;
    for (int i = x; i >= 1; i -= i & -i) {
        ans = max(ans, aib1[i]);
    }
    return ans;
}

int query2(int x) {
    x = cb(x);
    if (x == 0) {
        return 0;
    }
    int ans = 0;
    for (int i = x; i <= n; i += i & -i) {
        ans = max(ans, aib2[i]);
    }
    return ans;
}

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;
    }
}

// 8 4
// 1 2 3 4 3 4 5 8

void solve() {
    for (int i = n; i >= 1; i--) {
        dp2[i] = query2(a[i] + 1) + 1;
        update2(a[i], dp2[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int cur = query1(a[i] + x - 1) + dp2[i];
        ans = max(ans, cur + 1);
        dp1[i] = query1(a[i] - 1) + 1;
        update1(a[i], dp1[i]);
    }
    cout << ans << "\n";
}

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