Submission #1274398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274398		warrenn	Global Warming (CEOI18_glo)	C++20	32 / 100	82 ms	6780 KiB

glo

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

int lis(vector<int>&a){
    vector<int>tmp;
    for(int q=0;q<a.size();q++){
        int id=lower_bound(tmp.begin(),tmp.end(),a[q])-tmp.begin();
        if(id==tmp.size()){
            tmp.push_back(a[q]);
        }
        else{
            tmp[id]=a[q];
        }
    }
    return tmp.size();
}

int pref[1000+2][42],suf[1000+2][42];

signed main(){
    int n,x;
    cin>>n>>x;
    vector<int>a;
    for(int q=0;q<n;q++){
        int x;
        cin>>x;
        a.push_back(x);
    }

    if(n<=1000){
        for(int q=0;q<=1001;q++){
            for(int w=0;w<=42;w++){
                pref[q][w]=1e18;
                suf[q][w]=-1e18;
            }
        }
        pref[0][0]=0;

        for(int q=1;q<=n;q++){
            for(int l=0;l<q;l++){
                pref[q][l]=min(pref[q][l],pref[q-1][l]);
                if(a[q-1]>pref[q-1][l]){
                    pref[q][l+1]=min(pref[q][l+1],a[q-1]);
                }
            }
        }

        suf[n+1][0]=1e18;
        for(int q=n;q>=1;q--){
            for(int l=0;l<=n-q+1;l++){
                suf[q][l]=max(suf[q][l],suf[q+1][l]);
                if(a[q-1]<suf[q+1][l]){
                    suf[q][l+1]=max(suf[q][l+1],a[q-1]);
                }
            }
        }

        int ans=0;
        for(int q=1;q<=n;q++){
            vector<int>tmp;
            for(int w=n;w>=0;w--){
                tmp.push_back(suf[q+1][w]);
            }
            for(int w=0;w<=q;w++){
                if(pref[q][w]!=1e18){
                    int id=upper_bound(tmp.begin(),tmp.end(),pref[q][w]-x)-tmp.begin();
                    ans=max(ans,w+(int)tmp.size()-1-id);

                }
            }
        }
        cout<<ans<<endl;
    }
    else if(x==0){
        cout<<lis(a)<<endl;
    }
    else if(x==1e9){
        int lis[n+1];
        lis[0]=0;
        vector<int>tmp;
        for(int q=1;q<=n;q++){
            int id=lower_bound(tmp.begin(),tmp.end(),a[q-1])-tmp.begin();
            if(id==tmp.size()){
                tmp.push_back(a[q-1]);
            }
            else{
                tmp[id]=a[q-1];
            }
            lis[q]=tmp.size();
        }
        tmp.clear();
        int lds[n+2]; lds[n+1]=0;
        for(int q=n;q>=1;q--){
            int id=lower_bound(tmp.begin(),tmp.end(),-a[q-1])-tmp.begin();
            if(id==tmp.size()){
                tmp.push_back(-a[q-1]);
            }
            else{
                tmp[id]=-a[q-1];
            }
            lds[q]=tmp.size();
        }

        int ans=0;
        for(int q=1;q<=n;q++){
            ans=max(ans,lis[q]+lds[q+1]);
        }
        cout<<ans<<endl;
    }
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:34:27: warning: iteration 42 invokes undefined behavior [-Waggressive-loop-optimizations]
   34 |                 pref[q][w]=1e18;
      |                 ~~~~~~~~~~^~~~~
glo.cpp:33:26: note: within this loop
   33 |             for(int w=0;w<=42;w++){
      |                         ~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25