Submission #970772

#	Time	Username	Problem	Language	Result	Execution time	Memory
970772		vjudge1	Global Warming (CEOI18_glo)	C++17	100 / 100	84 ms	5064 KiB

glo

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

const int mxN = 2e5+5;
int n, x, arr[mxN], dp[mxN];

int main() {
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    vector<int> lis;
    for(int i = 1; i <= n; ++i) {
        auto itr = lower_bound(lis.begin(), lis.end(), arr[i]);
        dp[i] = itr - lis.begin() + 1;
        if(itr == lis.end()) lis.emplace_back(arr[i]);
        else *itr = arr[i];
    }
    int ans = 0;
    vector<int> lds;
    for(int i = n; i >= 1; --i) {
        auto itr = lower_bound(lds.begin(), lds.end(), -arr[i]);
        int from_right = itr - lds.begin();
        ans = max(ans, dp[i] + from_right);
        arr[i] += x;
        auto itr2 = lower_bound(lds.begin(), lds.end(), -arr[i]);
        if(itr2 == lds.end()) lds.emplace_back(-arr[i]);
        else *itr2 = -arr[i];
    }
    cout << ans;
}

• 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