제출 #948541

#제출 시각아이디문제언어결과실행 시간메모리
948541dio_2Global Warming (CEOI18_glo)C++17
38 / 100
2065 ms27632 KiB
#include<bits/stdc++.h> using namespace std; struct MaxSegree{ MaxSegree () {} MaxSegree (int N){ build(N); } int base; const int neutral = -(int)1e9; vector<int> maxy; void build(int N){ base = 1; while(base <= N) base *= 2; maxy.assign(2 * base, neutral); } void pull(int node){ maxy[node] = max(maxy[2 * node], maxy[2 * node + 1]); } void update(int node, int lx, int rx, int pos, int val){ if(lx == rx){ assert(lx == pos); maxy[node] = val; return ; } int mid = (lx + rx) / 2; if(pos <= mid){ update(2 * node, lx, mid, pos, val); } else { update(2 * node + 1, mid + 1, rx, pos, val); } pull(node); } int Max(int node, int lx, int rx, int l, int r){ if(lx > r || rx < l) return neutral; if(l <= lx && rx <= r) return maxy[node]; int mid = (lx + rx) / 2; return max(Max(2 * node, lx, mid, l, r), Max(2 * node + 1, mid + 1, rx, l, r)); } void update(int pos, int val){ update(1, 1, base, pos, val); } int Max(int l, int r){ return Max(1, 1, base, l, r); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; vector<int> t(n); set<int> s; map<int, int> comp; for(int &y : t){ cin >> y; s.insert(y); } // compress for RMQ. int cnt = 1; for(int y : s){ comp[y] = cnt++; } MaxSegree LIS(n), LDS(n); vector<int> dp(n, 1), dp2(n, 1); for(int i = 0;i < n;i++){ if(comp[t[i]] - 1 >= 1){ dp[i] = max(dp[i], LIS.Max(1, comp[t[i]] - 1) + 1); } LIS.update(comp[t[i]], dp[i]); } int answer = *max_element(dp.begin(), dp.end()); if(x == 0){ cout << answer << '\n'; return 0; } for(int i = n - 1;i >= 0;i--){ if(comp[t[i]] + 1 <= n){ dp2[i] = max(dp2[i], LDS.Max(comp[t[i]] + 1, n) + 1); } LDS.update(comp[t[i]], dp2[i]); answer = max(answer, dp2[i]); if(i - 1 >= 0){ int prev_val = t[i - 1] - x; // find first strictly < for(int j = i;j < n;j++){ if(prev_val < t[j]){ answer = max(answer, dp[i - 1] + dp2[j]); } } } } cout << answer << '\n'; return 0; }
#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...