Submission #902266

#	Time	Username	Problem	Language	Result	Execution time	Memory
902266		Mohammadamin__Sh	Global Warming (CEOI18_glo)	C++17	100 / 100	378 ms	39508 KiB

glo

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 2e5 + 5, MOD = 1e9 + 7 , MAX = 1e9+10 , LG = 30;
const ll INF = 1e18 + 100;

int n , x , a[maxn] , dp[maxn] , maxi[4*maxn*LG] , Lc[4*maxn*LG] , Rc[4*maxn*LG] , now = 2 , ans[maxn];

void Update(int id , int L , int R , int idx , int val){
	if(L+1 == R){
		maxi[id] = val;
		return;
	}
	int mid = (L+R) >> 1 ;
	if(idx < mid){
		if(!Lc[id]) Lc[id] = now++;
		Update(Lc[id] , L , mid , idx , val);
	}
	else{
		if(!Rc[id]) Rc[id] = now++;
		Update(Rc[id] , mid , R , idx , val);
	}
	maxi[id] = max(maxi[Lc[id]] , maxi[Rc[id]]);
}

int Get(int id , int L , int R , int l , int r){
	if(id == 0) return 0;
	if(L == l and R == r) return maxi[id];
	int mid = (L+R) >> 1 , res = 0;
	if(l < mid) res = max(res , Get(Lc[id] , L , mid , l , min(r , mid)));
	if(r > mid) res = max(res , Get(Rc[id] , mid , R , max(l , mid) , r));
	return res;
}

int32_t main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	
	cin >> n >> x;
	for(int i = 1 , x ; i <= n ; i++) cin >> a[i];
	for(int i = 1 ; i <= n ; i++){
		dp[i] = Get(1 , 1 , MAX  , 1 , a[i]) + 1;
		Update(1 , 1 , MAX , a[i] , dp[i]);
	}
	for(int i = 1 ; i <= now ; i++) Lc[i] = Rc[i] = maxi[i] = 0;
	now = 2;
	for(int i = n ; i >= 1 ; i--){
		ans[i] = dp[i] + Get(1 , 1 , MAX , max(a[i] - x + 1, 1) , MAX);
		Update(1 , 1 , MAX , a[i] , Get(1 , 1 , MAX , a[i] + 1 , MAX) + 1);
		
	}
	cout << *max_element(ans+1 , ans+n+1);
	
}

Compilation message (stderr)

glo.cpp: In function 'int32_t main()':
glo.cpp:51:18: warning: unused variable 'x' [-Wunused-variable]
   51 |  for(int i = 1 , x ; i <= n ; i++) cin >> 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