Submission #375953

#	Time	Username	Problem	Language	Result	Execution time	Memory
375953		YJU	Global Warming (CEOI18_glo)	C++14	62 / 100	55 ms	7528 KiB

glo

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e6+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

vector<ll> lis;
ll n,d,u[N],val[N],pre[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>d;
	REP(i,n)cin>>u[i];
	for(int i=n-1;i>=0;i--){
		if(SZ(lis)==0||u[i]<lis.back()){
			lis.pb(u[i]);
		}else{
            ll l=-1,r=SZ(lis)-1;
            while(r-1>l){
                ll mid=(r+l)>>1;
                if(lis[mid]<=u[i])r=mid;
                else l=mid;
            }
            lis[r]=u[i];
		}
		//REP(j,SZ(lis))cout<<lis[j]<<(j==SZ(lis)-1?"\n":" ");
		val[i]=(SZ(lis)?lis.back():-INF);
		pre[i]=SZ(lis);
	}
	ll ans=pre[0];
	lis.clear();
	REP(i,n){
		ll id=(lwb(lis.begin(),lis.end(),val[i]+d)-lis.begin());
		//cout<<id<<" "<<u[id]<<" "<<val[i]<<" "<<pre[i]<<"\n";
		ans=max(ans,id+pre[i]);
        if(SZ(lis)==0||u[i]>lis.back()){
			lis.pb(u[i]);
        }else{
			*lwb(lis.begin(),lis.end(),u[i])=u[i];
        }
	}
	cout<<ans<<"\n";
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0


*/

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