Submission #704149

#	Time	Username	Problem	Language	Result	Execution time	Memory
704149		KLPP	Global Warming (CEOI18_glo)	C++14	100 / 100	110 ms	10944 KiB

glo

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

class FT{
	vector<lld> F;
	public:
	void init(int n){
		F.clear();
		F.resize(n+1,-1e18);
	}
	void update(int pos, lld val){
		pos++;
		if(pos==0)return;
		for(;pos<(int)F.size();pos+=(pos&(-pos))){
			F[pos]=max(F[pos],val);
		}
	}
	lld query(int pos){
		pos++;
		if(pos==0)return -1e18;
		lld ans=-1e18;
		for(;pos>0;pos-=(pos&(-pos))){
			//cout<<"A"<<" "<<pos<<endl;
			ans=max(ans,F[pos]);
		}
		return ans;
	}
};
FT F;
void solve(){
	/*freopen("talent.in", "r", stdin);
	freopen("talent.out", "w", stdout);*/
	int n;
	lld x;
	cin>>n>>x;
	vector<lld> V(n);
	for(auto &y:V)cin>>y;
	vector<lld> L;
	vector<lld> pref(n),suf(n);
	auto apply=[&](vector<lld> &obj, bool invert){
		L.clear();
		rep(i,0,n){
			int lo=-1;
			int hi=L.size();
			while(hi-lo>1){
				int mid=(hi+lo)/2;
				if(!invert){
					if(L[mid]<V[i])lo=mid;
					else hi=mid;
				}else{
					if(L[mid]>V[i])lo=mid;
					else hi=mid;
				}
			}
			if(hi==(int)L.size())L.push_back(V[i]);
			L[hi]=V[i];
			obj[i]=hi+1;
		}
		return;
	};
	apply(pref,0);
	reverse(V.begin(),V.end());
	apply(suf,1);
	reverse(V.begin(),V.end());
	reverse(suf.begin(),suf.end());
	lld ans=(int)L.size();
	vector<lld> comp;
	trav(a,V)comp.push_back(a);
	sort(comp.begin(),comp.end());
	comp.resize(unique(comp.begin(),comp.end())-comp.begin());
	F.init(comp.size());
	//trav(a,comp)cout<<a<<"\n";
	rep(i,0,n){
		//cout<<V[i]+x<<" "<<lower_bound(comp.begin(),comp.end(),V[i]+x)-comp.begin()-1<<" "<<F.query(upper_bound(comp.begin(),comp.end(),V[i]+x)-comp.begin()-1)<<" "<<suf[i]<<endl;
		ans=max(ans,F.query(lower_bound(comp.begin(),comp.end(),V[i]+x)-comp.begin()-1)+suf[i]);
		F.update(lower_bound(comp.begin(),comp.end(),V[i])-comp.begin(),pref[i]);
		//cout<<lower_bound(comp.begin(),comp.end(),V[i])-comp.begin()<<" "<<pref[i]<<endl;
	}
	cout<<ans<<"\n";
}
	

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.precision(16);
	int tt=1;
	//cin>>tt;
	rep(test,0,tt){
		solve();
	}
}

• 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