Submission #609777

#	Time	Username	Problem	Language	Result	Execution time	Memory
609777		Pietra	Global Warming (CEOI18_glo)	C++14	100 / 100	467 ms	36808 KiB

glo

#include<bits/stdc++.h>
#define meio ((i+j)>>1)
using namespace std ; 

const int maxn = 2e5 + 5 ; 
const int MAX = 2e5 + 5 ; 
const int lmt = 2e9 + 5 ; 

int n, x, v[maxn], suf[maxn] ; 
vector<int> e, d, mx ; 

struct SEG{

	int node(){
		e.push_back(0), d.push_back(0), mx.push_back(0) ; 
		return max(0, (int)d.size() - 1) ; 
	}

	void upd(int no, int i, int j, int pos, int val){
		if(!no) return ;
		if(i == j){
			mx[no] = max(val, mx[no]) ; return ; 
		}
		if(pos <= meio){
			if(!e[no]){
				int aux = node() ; 
				e[no] = aux ; 
			}
			upd(e[no], i, meio, pos, val) ; 
		}
		else{
			if(!d[no]){
				int aux = node() ; 
				d[no] = aux ; 
			}
			upd(d[no], meio + 1, j, pos, val) ; 
		}
		mx[no] = max(mx[e[no]], mx[d[no]]) ; 
	}

	int query(int no, int i, int j, int l, int r){
		if(!no || l > j || r < i) return 0 ; 
		if(r >= j && l <= i) return mx[no] ; 
		return max(query(e[no], i, meio, l, r), query(d[no], meio + 1, j, l, r)) ; 
	}

} Seg ; 

int main(){

	ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 

	cin >> n >> x ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> v[i] ; 
		v[i]++ ; 
	}	

	Seg.node() ; Seg.node() ;

	for(int i = n ; i > 0 ; i--){
		int mx = Seg.query(1, 1, lmt, v[i] + 1, lmt) ; 
		Seg.upd(1, 1, lmt, v[i], mx + 1) ; 
		suf[i] = mx + 1 ; 
	}

	// for(int i = 1 ; i <= n ; i++) cout << suf[i] << " " ; 
	// cout << "\n" ; 

	int ans = Seg.query(1, 1, lmt, 1, lmt) ; 

	e.clear() ; d.clear() ; mx.clear() ; 
	Seg.node() ; Seg.node() ;

	for(int i = 1 ; i <= n ; i++){
		int val = Seg.query(1, 1, lmt, 1, v[i] - 1) ;
		int valor = Seg.query(1, 1, lmt, 1, v[i] + x - 1) ;
		ans = max(ans, suf[i] + valor) ; 
		Seg.upd(1, 1, lmt, v[i], val + 1) ; 
	} 

	cout << ans << "\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