제출 #375986

#제출 시각아이디문제언어결과실행 시간메모리
375986hivakaramiGlobal Warming (CEOI18_glo)C++14
0 / 100
272 ms8528 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define f first #define s second const int N = 2e5 + 100; const ll mod = 1e9 + 7; const ll inf = 1e16 + 100; int dp[N], a[N], l[N], r[N], n, x, seg[4*N]; vector<int> v; int get(int L, int R, int b = 0, int e = n, int ind = 1) { if(R <= b || e <= L) return 0; if(L <= b && e <= R) return seg[ind]; int mid = (b + e) / 2; return max(get(L, R, mid, e, ind*2+1), get(L, R, b, mid, ind*2)); } void add(int k, int val, int b = 0, int e = n, int ind = 1) { if(b + 1 == e) { seg[ind] = val; return; } int mid = (b + e) / 2; if(k < mid) add(k, val, b, mid, ind*2); else add(k, val, mid, e, ind*2+1); seg[ind] = max(seg[ind*2], seg[ind*2+1]); } int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> x; for(int i = 0; i < n; i++) { cin >> a[i]; v.push_back(a[i]); } sort(v.begin(), v.end()); int p = 1; for(int i = 0; i < n; i++) { int j = lower_bound(dp, dp+p, a[i]) - dp; dp[j] = a[i]; p = max(p, j+1); l[i] = j; } //cout << p - 1 << endl; memset(dp, 0, sizeof(dp)); p = 1; for(int i = n-1; i >= 0; i--) { int j = lower_bound(dp, dp+p, a[i]) - dp; dp[j] = a[i]; p = max(p, j+1); r[i] = j; } int ans = 1; for(int i = 0; i < n; i++) { int id = lower_bound(v.begin(), v.end(), a[i]+x) - v.begin(); int mx = get(0, id); ans = max(ans, r[i] + mx); id = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); add(id, l[i]); } cout << ans << endl; return 0; } /* 8 10 7 3 5 12 2 7 3 4 */
#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...