제출 #1172199

#제출 시각아이디문제언어결과실행 시간메모리
1172199ffeyyaeGlobal Warming (CEOI18_glo)C++20
100 / 100
37 ms2500 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5, INF = 1e9;
int n, x, ans;
int dp[N], keep[N];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    for( int i=0;i<n;i++ ) cin >> keep[i];
    vector<int> tp;
    for( int i=0;i<n;i++ )
    {
        int idx = lower_bound( tp.begin(), tp.end(), keep[i] )-tp.begin();
        if( idx == tp.size() ) tp.push_back( keep[i] );
        else tp[idx] = keep[i];
        dp[i] = idx+1;
        ans = max( ans, dp[i] );
    }
    tp.clear();
    for( int i=n-1;i>=0;i-- )
    {
        int idx = lower_bound( tp.begin(), tp.end(), -keep[i]+x )-tp.begin();
        int temp = lower_bound( tp.begin(), tp.end(), -keep[i] )-tp.begin();
        if( temp == tp.size() ) tp.push_back( -keep[i] );
        else tp[temp] = -keep[i];
        ans = max( ans, dp[i]+idx );
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...