Submission #753683

#	Time	Username	Problem	Language	Result	Execution time	Memory
753683		sheldon	Global Warming (CEOI18_glo)	C++14	62 / 100	59 ms	10800 KiB

glo

#include <bits/stdc++.h>

using namespace std;

void solve() {

    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    vector<int> dp1, dp2;
    vector<vector<int>> prev(n);
    vector<int> where(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        int l = 0, r = (int) dp2.size() - 1;
        int idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (dp2[mid] > a[i]) {
                l = mid + 1;
            } else if (dp2[mid] < a[i]) {
                r = mid - 1;
                idx = mid;
            } else {
                idx = mid;
                break;
            }
        }
        if (idx == -1) {
            dp2.push_back(-1);
            idx = dp2.size() - 1;
        }
        where[i] = idx;
        prev[idx].push_back(a[i]);
        dp2[idx] = a[i];
    }
    int ans = -1;
    for (int i = 0; i < n; ++i) {
        int loc = where[i];
        prev[loc].pop_back();
        if (prev[loc].empty()) {
            dp2.pop_back();
        } else {
            dp2[loc] = prev[loc].back();
        }
        auto it = lower_bound(dp1.begin(), dp1.end(), a[i] - x);
        if (it == dp1.end()) {
            dp1.push_back(a[i] - x);
        } else {
            *it = a[i] - x;
        }
        int l = 0, r = (int) dp2.size() - 1;
        int idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (dp2[mid] > dp1.back()) {
                idx = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans = max(ans, (int) dp1.size() + idx + 1);
    }
    cout << max(ans, (int) dp1.size());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

• 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