Submission #1090638

#TimeUsernameProblemLanguageResultExecution timeMemory
1090638NurislamGlobal Warming (CEOI18_glo)C++17
10 / 100
196 ms13876 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int inf = 1e10, N = 2e5+5; //int mod = 998244353 //int mod = 1000000007; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) struct segtree{ vector<int> t; segtree(){ t.resize(N*4); }; void upd(int ps, int val, int i = 1, int l = 1, int r = N){ if(l == r){ t[i] = val; return; } int m = (l+r)>>1; if(ps <= m)upd(ps, val, i*2, l, m); else upd(ps, val, i*2+1, m+1, r); t[i] = max(t[i*2], t[i*2+1]); }; int get(int l, int r, int tl = 1, int tr = N, int i = 1){ if(tl > r || tr < l || tl > tr)return 0; if(l <= tl && tr <= r)return t[i]; int m = (tl+tr)>>1; return max(get(l, r, tl, m, i*2), get(l, r, m+1, tr, i*2+1)); }; }; void solve(){ int n, x; cin >> n >> x; vector<int> a(n+1); for(int i = 1; i <= n; i++)cin >> a[i]; vector<int> init = a; vector<int> s; s = a;s.pb(-inf);s.pb(inf); sort(all(s)); s.erase(unique(all(s)), s.end()); for(int &i:a)i = lower_bound(all(s), i) - s.begin(); auto id = [&](int x, int t) -> int{ int l = lower_bound(all(s), x)-s.begin(); while(t == 0 && s[l] < x)l++; while(t == 1 && s[l] > x)l--; return l; }; segtree t; vector<int> lis;lis.pb(0); for(int i = 1; i <= n; i++){ int l = lower_bound(all(lis), a[i])-lis.begin(); if(l == (int)lis.size()) lis.pb(a[i]); else lis[l] = a[i]; t.upd(a[i], l); //cout << l << ' '; } //cout << '\n'; int ans = lis.size() - 1; lis.clear(); lis.pb(-inf); for(int i = n; i >= 1; i--){ int l = lower_bound(all(lis), -a[i]) - lis.begin(); if(l == (int)lis.size()) lis.pb(-a[i]); else lis[l] = -a[i]; t.upd(a[i], 0); //cout << t.get(id(a[i]-x+1, 0), id(a[i]+x-1, 1)) << ' '; //cout << id(init[i]-x+1, 0) << ' ' << id(init[i]+x-1, 1) << '\n'; //cout << init[i]-x+1 << ' ' << init[i]+x-1 << '\n'; chmax(ans, l + t.get(id(init[i]-x, 0), id(init[i]+x, 1))); } //cout << '\n'; cout << ans << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#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...