Submission #1120036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120036		nikolashami	Global Warming (CEOI18_glo)	C++17	100 / 100	1658 ms	37164 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;
}   

map<int,int>sigma,compress;
int st[4*N],ret;

void qry(int l,int r,int node=1,int tl=1,int tr=n){
    if(tl>=l&&tr<=r){
        ret=max(ret,sigma[st[node]]);
        return;
    }
    int mid=(tl+tr)/2;
    if(mid>=l)qry(l,r,node*2,tl,mid);
    if(mid+1<=r)qry(l,r,node*2+1,mid+1,tr);
}

void upd(int id,int val,int node=1,int tl=1,int tr=n){
    if(tl==tr){
        st[node]=val;
        return;
    }
    int mid=(tl+tr)/2;
    if(id<=mid)upd(id,val,node*2,tl,mid);
    else upd(id,val,node*2+1,mid+1,tr);
    if(sigma[st[node*2]]>sigma[st[node*2+1]])st[node]=st[node*2];
    else st[node]=st[node*2+1];
}

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();
    int omikron=0;

    vector<int>ljudi;
    for(int i=0;i<n;++i)
        ljudi.push_back(a[i]+x);

    sort(ljudi.begin(),ljudi.end());

    for(auto &z:ljudi)
        if(!compress[z])
            compress[z]=++omikron;

    set<int>zeta;

    fill(st,st+4*N,-1);

    for(int i=n-1;i>=0;--i){
        auto nx=zeta.upper_bound(a[i]);
        if(nx!=zeta.end()){
            int kompresovan=compress[*nx];
            ret=0;
            qry(kompresovan,n);
            ans=max(ans,ret+preflis[i]);
        }
        sigma[compress[a[i]+x]]=max(sigma[compress[a[i]+x]],suflds[i]);
        upd(compress[a[i]+x],compress[a[i]+x]);
        zeta.insert(a[i]+x);
    }
    
    cout<<ans;
}   

Compilation message (stderr)

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

• 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