제출 #1315037

#제출 시각아이디문제언어결과실행 시간메모리
1315037thanhbinh13Global Warming (CEOI18_glo)C++20
100 / 100
62 ms6660 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5+5; long long n,X,t[N]; long long b[N]; long long pre[N],suf[N]; long long bs1(long long x,long long l,long long r) { long long m = 0; while(l <= r) { long long mid = (l+r) /2; if (t[b[mid]] < x) { m = mid; l = mid+1; } else r = mid-1; } return b[m]; } long long bs2(long long x,long long l,long long r) { long long m = 0; while(l <= r) { long long mid = (l+r) /2; if (t[b[mid]] > x) { m = mid; l = mid+1; } else r = mid-1; } return b[m]; } long long bs3(long long x,long long l,long long r) { long long m = 0; while(l <= r) { long long mid = (l+r) /2; if (t[b[mid]] > x-X) { m = mid; l = mid+1; } else r = mid-1; } return b[m]; } long long bs4(long long x,long long l,long long r) { long long m = 0; while(l <= r) { long long mid = (l+r) /2; if (t[b[mid]] < x+X) { m = mid; l = mid+1; } else r = mid-1; } return b[m]; } long long ans = 0; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> X; for (int i= 1; i <= n;i ++) { cin >> t[i]; } long long res = 0; for (int i = 1; i <= n; i++) { b[i] = 0; } for (int i = 1;i <=n; i++) { pre[i] = pre[bs1(t[i],1,res)]+1; b[pre[i]] = i; res= max(res,pre[i]); } res = 0; for (int i = 1; i <= n; i++) { b[i] = 0; } for (int i = n;i >= 1; i--) { suf[i] = suf[bs2(t[i],1,res)]+1; b[suf[i]] = i; res= max(res,suf[i]); } res = 0; for (int i = 1; i <= n; i++) { b[i] = 0; } for (int i = n;i >= 1; i--) { // suf[i] = suf[bs(t[i],1,res)]+1; ans = max(ans,pre[i]+suf[bs3(t[i],1,res)]); b[suf[i]] = i; res= max(res,suf[i]); } res = 0; for (int i = 1; i <= n; i++) { b[i] = 0; } for (int i = 1;i <= n; i++) { // suf[i] = suf[bs(t[i],1,res)]+1; ans = max(ans,pre[bs4(t[i],1,res)]+suf[i]); b[pre[i]] = i; res= max(res,pre[i]); } cout << ans; }
#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...