Submission #1271824

#TimeUsernameProblemLanguageResultExecution timeMemory
1271824win1702Global Warming (CEOI18_glo)C++20
62 / 100
33 ms5012 KiB
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define MAXN 200005
#define INF 1000000001
#define MOD 1000000007
#define FOR(i, l, r) for (int i = l; i <= r; ++i)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define BIT(x,i) ((x>>i)&1)
#define MASK(i) (1ll<<(i))
#define FILE ""

void fastip(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(FILE".inp","r")){
        freopen(FILE".inp","r",stdin);
        freopen(FILE".out","w",stdout);
    }
}

const int MAX=100005;
const int div2=(MOD+1)/2;


int n,x;
vector<int> lis1;
vector<int> lis2;
vector<int> lis;
vector<int> a;
vector<int> mn,mx;

void solve(){

    cin>>n>>x;
    a.resize(n+1);
    mn.resize(n+1,INF);
    mx.resize(n+1,-INF);
    lis1.resize(n+1,0);
    lis2.resize(n+1,0);

    FOR(i,1,n)
        cin>>a[i];

    FOR(i,1,n){
        int pos=lower_bound(lis.begin(),lis.end(),a[i])-lis.begin();
        if (pos==(int)lis.size()) lis.push_back(a[i]);
        else lis[pos]=a[i];
        lis1[i]=lis.size();
        mx[i]=lis.back();
    }
    lis.clear();

    FOD(i,n,1){
        int pos=lower_bound(lis.begin(),lis.end(),-a[i])-lis.begin();
        if (pos==(int)lis.size()) lis.push_back(-a[i]);
        else lis[pos]=-a[i];
        lis2[i]=lis.size();
        mn[i]=-lis.back();
    }
//
//    FOR(i,1,n) cout<<lis1[i]<<' ';cout<<'\n';
//    FOR(i,1,n) cout<<lis2[i]<<' ';cout<<'\n';
//    FOR(i,1,n) cout<<mx[i]<<' ';cout<<'\n';
//    FOR(i,1,n) cout<<mn[i]<<' ';cout<<'\n';

    int best=0;
    FOR(i,1,n) best=max(best,lis1[i]);

    FOR(i,1,n-1){
        if (mx[i]-x<mn[i+1]){
            best=max(best,lis1[i]+lis2[i+1]);
        }
    }

    cout<<best;

}


int main(){


    fastip();
    solve();
}

Compilation message (stderr)

glo.cpp: In function 'void fastip()':
glo.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(FILE".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(FILE".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...