Submission #607493

#	Time	Username	Problem	Language	Result	Execution time	Memory
607493		Pietra	Global Warming (CEOI18_glo)	C++14	0 / 100	2070 ms	9608 KiB

glo

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

const int maxn = 2e5 + 5 ; 

int n, x, v[maxn], tree[4*maxn] ; 
vector<int> vec ; 

struct SEG{

	void build(int no, int i, int j){
		if(i == j){
			tree[no] = 0 ; return ; 
		}
		build(esq, i, meio), build(dir, meio + 1, j) ;
		tree[no] = 0 ;  
	}

	int query(int no, int i, int j, int l, int r){
		if(l > j || r < i) return 0 ; 
		if(r >= j && l <= i) return tree[no] ; 
		return max(query(esq, i, meio, l, r), query(dir, meio + 1, j, l, r)) ;  
	}

	void upd(int no, int i, int j, int pos, int val){
		if(i == j){
			tree[no] = max(tree[no], val) ; 
			return ; 
		}
		if(pos <= meio) upd(esq, i, meio, pos, val) ; 
		else upd(dir, meio + 1, j, pos, val) ; 
		tree[no] = max(tree[esq], tree[dir]) ; 
	}

} Seg ; 

void solve_1(){

	int ans = 0 ; 

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

	ans = max(ans, Seg.query(1, 1, n+x+x+2, 1, n)) ; 

	cout << ans << "\n" ; 

}

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

	// cout << l << " " << r << " " << val << "\n" ; 

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

	Seg.build(1, 1, n+x+x+2) ; 
    
	int ans = 0 ;

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

	ans = max(ans, Seg.query(1, 1, n+x+x+2, 1, n)) ;

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

	return ans ; 

}

void solve_2(){

	for(int i = 1 ; i <= n ; i++) v[i] += (x+1) ; 

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

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

	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] ; 
		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 ; 

	if(x == 0) solve_1() ; 
    else solve_2() ; 

}

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