Submission #1103959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103959		vjudge1	Global Warming (CEOI18_glo)	C++17	62 / 100	37 ms	6708 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define int long long
int val[200010];
int highest[200010];
int sz[200010];
int lis[200010];
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,x;
    cin >> n >> x;
    for(int i= 0;i<n;i++){
        cin >> val[i];
    }
    int size=  0;
    int ans = 0;
    for(int i = 0;i<n;i++){    
        int idx = lower_bound(lis,lis+size,val[i])-lis;
        if(idx==size)size++;
        lis[idx] = val[i];
        highest[i] = lis[size-1];
        sz[i] = size;
    }
    ans = size;
    memset(lis,0,sizeof(lis));
    size = 0;
    for(int i = n-1;i>=1;i--){
        int idx = lower_bound(lis,lis+size,-(val[i]+x))-lis;
        if(idx==size)size++;
        lis[idx] = -(val[i]+x);
        int id = lower_bound(lis,lis+size,-highest[i-1])-lis;
        ans = max(ans,id+sz[i-1]);
    }
    ans = max(ans,size);
    cout << ans;
}

• 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