Submission #607503

#	Time	Username	Problem	Language	Result	Execution time	Memory
607503		Pietra	Global Warming (CEOI18_glo)	C++14	5 / 100	2056 ms	320 KiB

glo

// sequencia de dias q a temperatura foi estritamente crescente 
// pode escolher um inteiro d [-x, x] p somar num intervalo qlqr 
// p tentar tornar a lis maior 
// parcial -> bruta o x bruta o intervalo q vai somar/subtrair -> faz lis 
// x = 0 -> lis normal 
#include<bits/stdc++.h>
#define ll long long
using namespace std ; 

const int maxn = 55 + 5 ; 
const ll inf = 1e12 + 1 ;

int n, x ; 
ll v[maxn] ; 
map<ll,int> bit ;

struct BIT{
     
    void upd(ll pos, int val){
        if(pos <= 0) return ;
        for(; pos < 4*inf ; pos += pos&-pos) bit[pos] = max(bit[pos], val) ;
    }
     
    int query(ll pos){
        if(pos <= 0) return 0 ;
        int tot = 0 ;
        for(; pos > 0 ; pos -= pos&-pos) tot = max(tot, bit[pos]) ;
        return tot ;
    }
    
} Bit ;

void solve_1(){

	ll val = 0 ; 

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

    int ans = Bit.query(val+1) ; 

	cout << ans << "\n" ; 

}

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

	// cout << l << " " << r << " " << val << "\n" ; 
	bit.clear() ; 

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

	ll va = 0 ; 

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

    int ans = Bit.query(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 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" ; 

}

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] += (x + 1) ; 
	}	

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

}

• Subtask 1: 5 / 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