Submission #444986

#TimeUsernameProblemLanguageResultExecution timeMemory
444986Nima_NaderiGlobal Warming (CEOI18_glo)C++14
100 / 100
254 ms19652 KiB
//In the name of GOD //#pragma GCC optimize("O2") #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MXN = 1e6 + 10; const ll INF = 1e18; ll n, d, lans, ans; ll A[MXN], B[MXN], M[MXN], Mp[MXN]; ll dp[MXN], mx[MXN], rig[MXN]; vector<ll> Num; ll GetId(ll x){ return lower_bound(Num.begin(), Num.end(), x) - Num.begin() + 1; } void LIS(ll up, bool f){ dp[0] = -INF, mx[0] = lans = 0; for(int i = 1; i <= up; i ++) dp[i] = INF; for(int i = 1; i <= up; i ++){ if(f) rig[n - i + 1] = lower_bound(dp, dp + lans + 1, Mp[i]) - dp; mx[i] = lower_bound(dp, dp + lans + 1, M[i]) - dp; if(!f) ans = max(ans, mx[i] + rig[i] - 1); lans = max(lans, mx[i]); dp[mx[i]] = M[i]; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); cin >> n >> d; for(int i = 1; i <= n; i ++){ cin >> A[i], B[i] = A[i] - d; Num.push_back(A[i]); Num.push_back(B[i]); Num.push_back(-A[i]); Num.push_back(-B[i]); } sort(Num.begin(), Num.end()); Num.resize(unique(Num.begin(), Num.end()) - Num.begin()); for(int i = 1; i <= n; i ++) M[i] = GetId(-A[n - i + 1]); for(int i = 1; i <= n; i ++) Mp[i] = GetId(-B[n - i + 1]); LIS(n, 1); for(int i = 1; i <= n; i ++) M[i] = GetId(A[i]); LIS(n, 0); ans = max(ans, lans); cout << ans << '\n'; return 0; } // NNG
#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...