Submission #464934

#	Time	Username	Problem	Language	Result	Execution time	Memory
464934		_Avocado_	Global Warming (CEOI18_glo)	C++14	100 / 100	656 ms	22236 KiB

glo

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

vector<int>seg;

void update(int k, int v, int pos, int l, int r){
	if(l == r){
		seg[pos] = v;
		return;
	}
	if(k <= (l+r)/2) update(k, v, pos*2, l, (l+r)/2);
	else update(k, v, pos*2+1, (l+r)/2+1, r);
	
	seg[pos] = max(seg[pos*2], seg[pos*2+1]);
}

int query(int ql, int qr, int pos, int l, int r){
	if(l >= ql && r <= qr) return seg[pos];
	else if(l > qr || r < ql) return 0;
	else return max(query(ql, qr, pos*2, l, (l+r)/2), query(ql, qr, pos*2+1, (l+r)/2+1, r));
}

int bsearch(vector<int>&v, int val, int n){
	int r = n-1;
	int l = -1;
	
	while(r-l > 1){
		int x = (r+l)/2;
		if(v[x] > val) r = x;
		else l = x;
	}
	
	return v[r];
}

void print_tree(){
	int cut = 1;
	
	for(int i = 1; i<seg.size(); ++i){
		cout<<seg[i]<<" ";
		if(i == cut){
			cut = cut*2+1;
			cout<<endl;
		}
	}
	
	cout<<endl<<endl;
}
	

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, d; cin>>n>>d;
	
	seg.assign(n*4, 0);
	
	vector<int>v(n);
	vector<int>fred(n);
	
	for(int i = 0; i<n; ++i){
		int a; cin>>a;
		v[i] = a;
		fred[i] = a;
	}
	
	//for(auto u: v) cout<<u<<" ";
	//cout<<endl;
	
	sort(fred.begin(), fred.end());
	
	//for(auto u: fred) cout<<u<<" ";
	//cout<<endl;
	
	
	unordered_map<int, int>mp;
	
	for(int i = 0; i<n; ++i){
		mp[fred[i]] = i;
	}
	
	vector<int>lis(n);
	
	for(int i = 0; i<n; ++i){
		int cur;
		if(mp[v[i]] == 0) cur = 1;
		else cur = query(0, mp[v[i]]-1, 1, 0, n-1)+1;
		lis[i] = cur;
		update(mp[v[i]], cur, 1, 0, n-1);
	}
	
	//print_tree();
	
	
	//for(auto u: lis) cout<<u<<" ";
	//cout<<endl;
	
	seg.assign(n*4, 0);
	
	int ans = 0;
	
	update(mp[v[n-1]], 1, 1, 0, n-1);
	
	//print_tree();
	
	for(int i = n-2; i>=0; --i){
		int cur = bsearch(fred, v[i]-d, n);
		//cout<<v[i]-d<<" "<<cur<<endl;
		int suffix;
		if(cur >= fred[n-1]) suffix = 0;
		else suffix = query(mp[cur], n-1, 1, 0, n-1);
		//cout<<suffix<<" "<<lis[i]<<" "<<i<<endl;
		ans = max(ans, suffix+lis[i]);
		int upd;
		if(mp[v[i]] == n-1) upd = 1;
		else upd = query(mp[v[i]]+1, n-1, 1, 0, n-1)+1;
		update(mp[v[i]], upd, 1, 0, n-1);
		
		//print_tree();
	}
		
	cout<<ans;
	
	
	cout<<'\n';
}

Compilation message (stderr)

glo.cpp: In function 'void print_tree()':
glo.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 1; i<seg.size(); ++i){
      |                 ~^~~~~~~~~~~

• 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