Submission #521141

#TimeUsernameProblemLanguageResultExecution timeMemory
521141Wayne_YanGlobal Warming (CEOI18_glo)C++17
62 / 100
152 ms11316 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>; int solve(int *arr, int n, int x){ int rev[n]; 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); bruh += suf[i+1].ff; cmax(ans, bruh); //debug(bruh); } //cmax(ans, (int)v.size()); return ans; } 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 = solve(arr, n, x); int ans2 = solve(rev, n, x); assert(ans == ans2); 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...