Submission #862602

#	Time	Username	Problem	Language	Result	Execution time	Memory
862602		Pekiban	Global Warming (CEOI18_glo)	C++17	100 / 100	47 ms	5460 KiB

glo

#include <bits/stdc++.h>

using namespace std;

void solve(int l[], int t[], int n) {
    vector<int> v = {t[0]}; l[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (t[i] > v.back()) {
            v.push_back(t[i]);
            l[i] = v.size();
        }
        else {
            int x = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[x] = t[i];
            l[i] = x+1;
        }
    }
}
int x;
void solvee(int r[], int t[], int n) {
    reverse(t, t+n);
    for (int i = 0; i < n; ++i) {
        t[i] = -t[i];
    }
    vector<int> v = {t[0]};
    r[0] = 1;
    for (int i = 1; i < n; ++i) {
        int z = lower_bound(v.begin(), v.end(), t[i] + x) - v.begin();
        r[i] = z + 1;
        if (v.back() < t[i]) {
            v.push_back(t[i]);
        }
        else if (v.back() < t[i]+x) {
            int a = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[a] = t[i];
        }
        else {
            int y = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
            v[y] = t[i];
        }
    }
    reverse(r, r+n);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> x;
    int t[n];
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    int l[n], r[n];
    solve(l, t, n);
    solvee(r, t, n);
    int ans = l[n-1];
    for (int i = 0; i < n; ++i) {
        ans = max(ans, l[i] + r[i] - 1);
    }
    cout << ans << '\n';
    return 0;
}

• 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