Submission #1152130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152130		AlgorithmWarrior	Global Warming (CEOI18_glo)	C++20	100 / 100	87 ms	4308 KiB

glo

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const INF=2e9+5;
int v[MAX];
int n,d;

void read(){
    cin>>n>>d;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
}

int bin_search_mic(int v[],int n,int val){
    int st=0,dr=n;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(v[mij]<=val)
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

int bin_search_mare(int v[],int n,int val){
    int st=0,dr=n;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(v[mij]>=val)
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

int incr[MAX];
int vmin[MAX];

void find_increasing(){
    int i;
    for(i=1;i<=n;++i)
        vmin[i]=INF;
    vmin[0]=-INF;
    for(i=1;i<=n;++i){
        incr[i]=bin_search_mare(vmin,n,v[i]+d);
        int pos=bin_search_mare(vmin,n,v[i]);
        vmin[pos]=v[i];
    }
}

int decr[MAX];
int vmax[MAX];

void find_decreasing(){
    int i;
    for(i=1;i<=n;++i)
        vmax[i]=-INF;
    vmax[0]=INF;
    for(i=n;i;--i){
        int pos=bin_search_mic(vmax,n,v[i]);
        decr[i]=pos;
        vmax[pos]=v[i];
    }
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

int solve(){
    int maxim=0;
    int i;
    for(i=1;i<=n;++i)
        maxself(maxim,incr[i]+decr[i]-1);
    return maxim;
}

int main()
{
    read();
    find_increasing();
    find_decreasing();
    cout<<solve();
    return 0;
}

• 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