Submission #1022485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022485		handlename	Global Warming (CEOI18_glo)	C++17	100 / 100	41 ms	6360 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
long long n,x,arr[200001],ans[200001];
long long res;
void runtc(){
    cin>>n>>x;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
    }
    //can consider only decrementing
    //only need consider decrement [1,x]
    //try to "fix" x
    //find LIS for prefix and suffix
    vector<long long> lol;
    for (int i=1;i<=n;i++){
        int pos=lower_bound(lol.begin(),lol.end(),arr[i])-lol.begin();
        if (pos>=lol.size()){
            lol.pb(arr[i]);
        }
        else {
            lol[pos]=arr[i];
        }
        ans[i]=pos+1;
        res=max(res,ans[i]);
    }
    lol.clear();
    for (int i=n;i>=1;i--){
        int pos=lower_bound(lol.begin(),lol.end(),-(arr[i]-x))-lol.begin();
        res=max(res,ans[i]+pos);
        pos=lower_bound(lol.begin(),lol.end(),-(arr[i]))-lol.begin();
        if (pos>=lol.size()){
            lol.pb(-arr[i]);
        }
        else {
            lol[pos]=-arr[i];
        }
    }
  
    cout<<res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("pcb.in","r",stdin);
    // freopen("pcb.out","w",stdout);
    //freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Compilation message (stderr)

glo.cpp: In function 'void runtc()':
glo.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (pos>=lol.size()){
      |             ~~~^~~~~~~~~~~~
glo.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (pos>=lol.size()){
      |             ~~~^~~~~~~~~~~~

• 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