Submission #607577

#	Time	Username	Problem	Language	Result	Execution time	Memory
607577		Pietra	Global Warming (CEOI18_glo)	C++14	25 / 100	2099 ms	35000 KiB

glo

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

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

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

struct SEG{

	int node(){
		e.push_back(0), d.push_back(0), mx.push_back(0) ; 
		return max(0LL, (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]]) ; 
	}

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

	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 ; 


void solve_1(){

	e.clear(), d.clear(), mx.clear() ; 
    Seg.node() ; 
	Seg.node() ;
	
	int val = 0 ; 

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

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

	cout << ans << "\n" ; 

}

int try_val(int l, int r, int val){

	for(int i = l ; i <= r ; i++) v[i] += val ; 

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

	int va = 0 ; 

	for(int i = 1 ; i <= n ; i++){
        int mx = Seg.query(1, 1, lmt, 1, v[i] - 1) ;
        Seg.upd(1, 1, lmt, v[i], mx + 1) ;
        va = max(va, v[i]) ;
    }

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

	for(int i = l ; i <= r ; i++) v[i] -= val ; 

	return ans ; 

}

void solve_2(){

	int ans = try_val(1, n, 0) ; 

	for(int l = 1 ; l <= n ; l++){
		for(int r = l ; r <= n ; r++){
			ans = max(ans, try_val(l, r, x)) ; 
		}
	}

	cout << ans << "\n" ; 

}

int32_t 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]++ ; 
	}	

	if(x == 0){
		vector<int> vec ; 
		for(int i = 1 ; i <= n ; i++) vec.push_back(v[i]) ; 
		sort(vec.begin(), vec.end()) ; 
	    vec.erase(unique(vec.begin(), vec.end()), vec.end()) ; 
	    for(int i = 1 ; i <= n ; i++) v[i] = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin() + 1 ;  
		solve_1() ; 
	}
    else solve_2() ; 

}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25