Submission #553017

#TimeUsernameProblemLanguageResultExecution timeMemory
553017CyberSleeperGlobal Warming (CEOI18_glo)C++17
62 / 100
49 ms6412 KiB
#include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define debug(x) cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl #define all(x) x.begin(), x.end() #define fi first #define se second #define mp make_pair #define pb push_back #define ll long long #define ull unsigned long long #define pll pair<ll, ll> #define pii pair<int, int> #define ld long double #define nl endl #define tb '\t' #define sp ' ' #define sqr(x) (x)*(x) #define arr3 array<ll, 3> using namespace std; const ll MX=200005, MOD=1000000007, BLOCK=160, INF=2e9+7, LG=62; const ll INFF=1000000000000000007; const ld ERR=1e-6, pi=3.14159265358979323846; int N, K, A[MX], top[2][MX], cnt[2][MX], ans; vector<int> LIS; int main(){ fastio; cin >> N >> K; for(int i=1; i<=N; i++){ cin >> A[i]; } for(int i=1; i<=N; i++){ int tmp=A[i]; if(LIS.empty() || LIS.back()<tmp) LIS.pb(tmp); else LIS[lower_bound(all(LIS), tmp)-LIS.begin()]=tmp; top[0][i]=LIS.back(); cnt[0][i]=LIS.size(); } LIS.clear(); for(int i=N; i>0; i--){ int tmp=-A[i]; if(LIS.empty() || LIS.back()<tmp) LIS.pb(tmp); else LIS[lower_bound(all(LIS), tmp)-LIS.begin()]=tmp; top[1][i]=-LIS.back(); cnt[1][i]=LIS.size(); } ans=cnt[0][N]; for(int i=1; i<N; i++){ if(abs(top[0][i]-top[1][i+1])<K) ans=max(ans, cnt[0][i]+cnt[1][i+1]); } cout << ans << nl; }
#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...