Submission #1271826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271826		win1702	Global Warming (CEOI18_glo)	C++20	42 / 100	33 ms	4812 KiB

glo

#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];

    if (n==1){
        cout<<1;
        return;
    }

    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();
        if (i==n || lis2[i]!=lis2[i+1]) mn[i]=-lis.back();
        else mn[i]=mn[i+1];
    }
//
//    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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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