Submission #299848

#TimeUsernameProblemLanguageResultExecution timeMemory
299848thomas_liGlobal Warming (CEOI18_glo)C++17
100 / 100
67 ms4624 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pi = pair<int, int>; using pll = pair<ll, ll>; constexpr int INF = 0x3f3f3f3f; constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f; #define db(x) { cerr << #x << " = " << x << endl; } template<class RIt> void dbarr(RIt frs, RIt lst){ cerr << "arr: "; for(int i = 0; i < (int)(lst-frs); i++) cerr << frs[i] << " \n"[i==(int)(lst-frs)-1]; } #define all(x) begin(x), end(x) #define pb push_back #define eb emplace_back #define mpr make_pair #define fs first #define sn second const int MM = 2e5+5; int n,x,a[MM],l[MM],best[MM]; int main(){ //freopen("in.txt","r", stdin); cin.tie(0)->sync_with_stdio(0); cin >> n >> x; for(int i = 0; i < n; i++) cin >> a[i]; memset(l,0x3f,sizeof l); int ans = 0; for(int i = 0; i < n; i++){ int pos = lower_bound(l,l+n,a[i])-l; l[pos] = a[i]; best[i] = pos+1; ans = max(ans,best[i]); } memset(l,0x3f,sizeof l); for(int i = n-1; i >= 0; i--){ a[i] *= -1; int pos = lower_bound(l,l+n,a[i]+x)-l; int pos1 = lower_bound(l,l+n,a[i])-l; l[pos1] = a[i]; ans = max(ans,best[i]+pos); } cout << ans << "\n"; }
#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...