Submission #1120033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120033		nikolashami	Global Warming (CEOI18_glo)	C++17	45 / 100	1428 ms	262144 KiB

glo

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

const int N=2e5+4;
int a[N],preflis[N],suflds[N],n,x;

vector<int>dp;
int nadjipederaalnaopacke(int x){
    if(dp.empty()||x<dp.back())return dp.size();
    int l=0,r=dp.size();
    while(l<r){
        int m=(l+r)/2;
        if(dp[m]>x)
            l=m+1;
        else
            r=m;
    }
    return l;
}   

const int N2=31*2e5;
int lc[N2],rc[N2],st[N2],ret,m,c,id=1;
 
void make(int&node){
    if(!node)node=++id;
}

map<int,int>sigma;
 
void qry(int l,int r,int node=1,int tl=1,int tr=2e9){
    if(tl>=l&&tr<=r){
        ret=max(ret,sigma[st[node]]);
        return;
    }
    make(lc[node]);
    make(rc[node]);
    int mid=(tl+tr)/2;
    if(mid>=l)qry(l,r,lc[node],tl,mid);
    if(mid+1<=r)qry(l,r,rc[node],mid+1,tr);
}
 
void upd(int id,int val,int node=1,int tl=1,int tr=2e9){
    if(tl==tr){
        st[node]=val;
        return;
    }
    make(lc[node]);
    make(rc[node]);
    int mid=(tl+tr)/2;
    if(mid>=id)upd(id,val,lc[node],tl,mid);
    if(mid+1<=id)upd(id,val,rc[node],mid+1,tr);
    if(sigma[st[lc[node]]]>sigma[st[rc[node]]])st[node]=st[lc[node]];
    else st[node]=st[rc[node]];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>x;
    for(int i=0;i<n;++i)
        cin>>a[i]; 

    for(int i=0;i<n;++i){
        int id=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
        int sigma=-1;
        if(dp.empty()||a[i]>dp.back()){
            dp.push_back(a[i]);
            sigma=(dp.empty()?0:dp.size()-1);
        }
        else dp[id]=a[i];
        if(sigma==-1)sigma=id;
        preflis[i]=(sigma+1);
    }

    dp.clear();
    for(int i=n-1;i>=0;--i){
        int id=nadjipederaalnaopacke(a[i]);
        if(id==dp.size())dp.push_back(a[i]);
        else dp[id]=a[i];
        suflds[i]=(id+1);
    }

    int ans=dp.size();

    for(int i=n-1;i>=0;--i){
        ret=0;
        qry(a[i]+1,2e9);
        ans=max(ans,ret+preflis[i]);
        sigma[a[i]+x]=max(sigma[a[i]+x],suflds[i]);
        upd(a[i]+x,a[i]+x);
    }
    
    cout<<ans;
}   

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if(id==dp.size())dp.push_back(a[i]);
      |            ~~^~~~~~~~~~~

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