제출 #1084294

#제출 시각아이디문제언어결과실행 시간메모리
10842944QT0RGlobal Warming (CEOI18_glo)C++17
100 / 100
465 ms64960 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll wej[200003][2];

void init(ll &n, ll &x){
	cin >> n >> x;
	set<ll> s;
	map<ll,ll> mp;
	ll iter=0;
	for (ll i = 1; i<=n; i++){
		cin >> wej[i][0];
		s.insert(wej[i][0]);
		wej[i][1]=wej[i][0]+x;
		s.insert(wej[i][1]);
	}
	for (auto u : s)mp[u]=++iter;
	for (ll i = 1; i<=n; i++){
		wej[i][0]=mp[wej[i][0]];
		wej[i][1]=mp[wej[i][1]];
	}
}

const ll base=1<<19;
ll tree[2*base][2];
void change(ll v, ll x, ll ind){
	v+=base;
	tree[v][ind]=x;
	v>>=1;
	while(v){
		tree[v][ind]=max(tree[2*v][ind],tree[2*v+1][ind]);
		v>>=1;
	}
}
ll check(ll zas, ll ind){
	zas+=base+1;
	ll ans=0;
	while(zas){
		if (zas&1)ans=max(ans,tree[zas-1][ind]);
		zas>>=1;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,x;
	init(n,x);
	for (ll i = 1; i<=n; i++){
		change(wej[i][0],max(check(wej[i][0]-1,1),check(wej[i][1]-1,0))+1,1);
		change(wej[i][0],check(wej[i][0]-1,0)+1,0);
	}
	cout << max(check(base-2,0),check(base-2,1)) << '\n';
}
#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...