Submission #676496

#	Time	Username	Problem	Language	Result	Execution time	Memory
676496		penguin133	Global Warming (CEOI18_glo)	C++17	100 / 100	771 ms	22648 KiB

glo

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second


int P[300005], S[300005];
int n, x;
int A[300005], B[300005], C[300005];
int ft[300005];

void upd(int p, int v){
	for(;p<=n;p+=(p & -p))ft[p] = max(ft[p], v);
}

int query(int p){
	int res = 0;
	for(;p;p-=(p & -p))res = max(res, ft[p]);
	return res;
}
int32_t main(){
	cin >> n >> x;
	for(int i=1;i<=n;i++)cin >> A[i];
	map<int, int> mp;
	for(int i=1;i<=n;i++)C[i] = A[i];
	sort(C+1, C+n+1);
	int pre= -1e18, cnt = 0;
	for(int i=1;i<=n;i++){
		if(pre != C[i])mp[C[i]] = ++cnt;
		else mp[C[i]] = cnt;
		pre = C[i];
	}
	for(int i=1;i<=n;i++){
		P[i] = 1 + query(mp[A[i]] - 1);
		upd(mp[A[i]], P[i]);
	}
	for(int i=1;i<=n;i++)ft[i] = 0;
	for(int i=n;i>=1;i--){
		S[i] = 1 + query(n - mp[A[i]]);
		upd(n - mp[A[i]] + 1, S[i]);
	}
	for(int i=1;i<=n;i++){
		//cout << P[i].fi << " " << P[i].se << " " << S[i].fi << " " << S[i].se << '\n';
	}
	//for(int i=1;i<=n;i++)cout << mp[A[i]] << " ";
	//cout << '\n';
	int mini = 1e10;
	int ans = 0;
	for(int i=1;i<=n;i++)ft[i] = 0;
	for(int i=1;i<=n;i++){
		int res = A[i] + x;
		int s = 1, e = n, ans2 = 0;
		while(s <= e){
			int m = (s + e)>>1;
			if(C[m] < res)ans2 = m, s = m + 1;
			else e = m - 1;
		}
		ans = max(ans,query(mp[C[ans2]]) + S[i]);
		//cout << query(mp[C[ans2]]) + S[i].fi << '\n';
		upd(mp[A[i]], P[i]);
	}
	cout << ans;
}
	

Compilation message (stderr)

glo.cpp: In function 'int32_t main()':
glo.cpp:51:6: warning: unused variable 'mini' [-Wunused-variable]
   51 |  int mini = 1e10;
      |      ^~~~

• 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