Submission #133797

#	Time	Username	Problem	Language	Result	Execution time	Memory
133797		mirbek01	Global Warming (CEOI18_glo)	C++11	100 / 100	403 ms	13544 KiB

glo

# include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 3;

int n, x, a[N], b[N], t[N * 4];
int f[N], s[N], ans;
vector <int> vec;

void upd(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
	if(tl == tr){
		t[v] = max(t[v], val);
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			upd(pos, val, v << 1, tl, tm);
		else 
			upd(pos, val, v << 1 | 1, tm + 1, tr);
		t[v] = max(t[v << 1], t[v << 1 | 1]);
	}
}

int get(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
	if(l > tr || tl > r) 
		return 0;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) >> 1;
	return max(get(l, r, v << 1, tl, tm), 
				get(l, r, v << 1 | 1, tm + 1, tr));
}

int main(){
	cin >> n >> x;
	
	for(int i = 1; i <= n; i ++){
		scanf("%d", a+i);
		b[i] = a[i] + x;
		vec.push_back(a[i]);
		vec.push_back(b[i]);
 	}
	
	sort(vec.begin(), vec.end());
	vec.resize( unique(vec.begin(), vec.end()) - vec.begin() );
	
	for(int i = 1; i <= n; i ++){
		a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
		b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin() + 1;
	}
	
	for(int i = n; i >= 1; i --){
		s[i] = get(b[i] + 1, N - 1) + 1;
		upd(b[i], s[i]);
		ans = max(ans, s[i]);
	}
		
	memset(t, 0, sizeof(t));

	for(int i = 1; i <= n; i ++){
		ans = max(ans, get(1, b[i] - 1) + s[i]);
		f[i] = get(1, a[i] - 1) + 1;
		upd(a[i], f[i]);
	}
	
	cout << ans << endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+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