제출 #163780

#제출 시각아이디문제언어결과실행 시간메모리
163780Alexa2001Global Warming (CEOI18_glo)C++17
100 / 100
231 ms7076 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 2e5 + 5; pair<int,int> a[Nmax]; int A[Nmax]; int dp1[Nmax], dp2[Nmax]; int X, n; class AIB { int b[Nmax]; int query(int p) { int ans = 0; for(; p<=n; p+=ub(p)) ans = max(ans, b[p]); return ans; } void update(int p, int val) { for(; p; p-=ub(p)) b[p] = max(b[p], val); } int ub(int x) { return (x&(-x)); } public: void clear() { memset(b, 0, sizeof(b)); } int query_greater(int x) { int p = lower_bound(a+1, a+n+1, make_pair(x+1, 0)) - a; return query(p); } void update_greater(int x, int val) { int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a; update(p, val); } int query_smaller(int x) { int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a - 1; return query(n + 1 - p); } void update_smaller(int x, int val) { int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a; update(n+1-p, val); } } aib; void norm() { int i; for(i=1; i<=n; ++i) a[i] = {A[i], i}; sort(a+1, a+n+1); } void solve() { int i; aib.clear(); for(i=n; i; --i) { dp2[i] = aib.query_greater(A[i]) + 1; aib.update_greater(A[i], dp2[i]); } int ans = 0; aib.clear(); for(i=1; i<=n; ++i) { int curr_ans = aib.query_smaller(A[i] + X) + dp2[i]; ans = max(ans, curr_ans); dp1[i] = aib.query_smaller(A[i]) + 1; aib.update_smaller(A[i], dp1[i]); } cout << ans << '\n'; } int main() { // freopen("input", "r", stdin); cin.sync_with_stdio(false); cin.tie(0); cin >> n >> X; int i; for(i=1; i<=n; ++i) cin >> A[i]; norm(); solve(); 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...