Submission #521017

#TimeUsernameProblemLanguageResultExecution timeMemory
521017Wayne_YanGlobal Warming (CEOI18_glo)C++17
62 / 100
105 ms7868 KiB
#include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; #define int long long typedef int64_t ll; typedef long double ld; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb emplace_back #define mp make_pair #define mt make_tuple #define pii pair<int,int> #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define RF(n) RFi(i,n) #define RFi(i,n) RFl(i,0,n) #define RFl(i,l,n) for(int i=n-1;i>=l;i--) #define all(v) begin(v),end(v) #define siz(v) (ll(v.size())) #define get_pos(v,x) (lower_bound(all(v),x)-begin(v)) #define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v)) #define mem(v,x) memset(v,x,sizeof v) #define ff first #define ss second #define mid ((l+r)>>1) #define RAN(a,b) uniform_int_distribution<int> (a, b)(rng) #define debug(x) (cerr << (#x) << " = " << x << "\n") #define cmax(a,b) (a = max(a,b)) #define cmin(a,b) (a = min(a,b)) template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >; template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >; template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; signed main(){ int n,x; cin >> n >> x; int arr[n]; int rev[n]; F(n) cin >> arr[i]; F(n) rev[i] = -arr[n-1-i]; int ans = 0; pii suf[n]; // (length, greatest) vector<int> v; F(n){ int c = get_pos(v, rev[i]); if(c == (int)v.size()){ v.pb(rev[i]); }else{ cmin(v[c], rev[i]); } suf[n-1-i] = mp((int)v.size(), -v.back()); } //F(n) printf("%d %d\n", suf[i].ff, suf[i].ss); v.clear(); F(n){ int c = get_pos(v, arr[i]); if( c == (int) v.size()){ v.pb(arr[i]); }else{ cmin(v[c], arr[i]); } if(i == n-1) break; int bruh = get_pos(v, suf[i+1].ss + x); if(bruh != (int)v.size() && v[bruh] == suf[i+1].ss + x) bruh--; cmax(ans, suf[i+1].ff + bruh); } cmax(ans, (int)v.size()); printf("%lld", ans); return 0; }
#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...