제출 #607515

#제출 시각아이디문제언어결과실행 시간메모리
607515PietraGlobal Warming (CEOI18_glo)C++14
25 / 100
390 ms5264 KiB
#include<bits/stdc++.h> #define int long long using namespace std ; const int maxn = 2e5 + 5 ; const int inf = 1e4 + 1 ; const int MAX = 2e5 + 5 ; int n, x, v[maxn] ; int bit[6*inf] ; int bit2[MAX] ; struct BIT{ void upd(int pos, int val){ if(pos <= 0) return ; for(; pos < 4*inf ; pos += pos&-pos) bit[pos] = max(bit[pos], val) ; } int query(int pos){ if(pos <= 0) return 0 ; int tot = 0 ; for(; pos > 0 ; pos -= pos&-pos) tot = max(tot, bit[pos]) ; return tot ; } } Bit ; struct BIT2{ void upd2(int pos, int val){ if(pos <= 0) return ; for(; pos < MAX ; pos += pos&-pos) bit2[pos] = max(bit2[pos], val) ; } int query2(int pos){ if(pos <= 0) return 0 ; int tot = 0 ; for(; pos > 0 ; pos -= pos&-pos) tot = max(tot, bit2[pos]) ; return tot ; } } Bit2 ; void solve_1(){ int val = 0 ; for(int i = 1 ; i <= n ; i++){ int mx = Bit2.query2(v[i] - 1) ; Bit2.upd2(v[i], mx + 1) ; val = max(val, v[i]) ; } int ans = Bit2.query2(val+1) ; cout << ans << "\n" ; } int try_val(int l, int r, int val){ // cout << l << " " << r << " " << val << "\n" ; for(int i = 1 ; i < inf ; i++) bit[i] = 0 ; for(int i = l ; i <= r ; i++) v[i] += val ; int va = 0 ; for(int i = 1 ; i <= n ; i++){ int 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" ; } 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] += (x + 1) ; } 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() ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...