제출 #116158

#제출 시각아이디문제언어결과실행 시간메모리
116158JohnTitorGlobal Warming (CEOI18_glo)C++11
42 / 100
50 ms4212 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Global" int n, x; int a[200001]; int l[200001]; vector <int> f; int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(x); FOR(i, 1, n) read(a[i]); f.pb(-1e9); FOR(i, 1, n){ if(a[i]>f.back()){ l[i]=f.size(); f.pb(a[i]); } else{ l[i]=lower_bound(f.begin(), f.end(), a[i])-f.begin(); f[l[i]]=min(f[l[i]], a[i]); } } f.clear(); f.pb(1.5e9); int ans=0; DFOR(i, n, 1){ int t=a[i]-x; if(t<f.back()) ans=max(ans, (int)(l[i]+f.size()-1)); else ans=max(ans, (int)(l[i]+lower_bound(f.begin(), f.end(), a[i], greater <int>())-f.begin()-1)); if(a[i]<f.back()) f.pb(a[i]); else{ t=lower_bound(f.begin(), f.end(), a[i], greater <int>())-f.begin(); f[t]=max(f[t], a[i]); } } writeln(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...