Submission #1084294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084294		4QT0R	Global Warming (CEOI18_glo)	C++17	100 / 100	465 ms	64960 KiB

glo

#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';
}

• 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