Submission #1226757

#TimeUsernameProblemLanguageResultExecution timeMemory
1226757yassiaGlobal Warming (CEOI18_glo)C++20
22 / 100
524 ms36828 KiB
#ifndef local #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; using pll = pair<ll,ll>; using str = string; using ld = long double; auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rnd(sd); ll d1[1ll<<21]; ll d2[1ll<<21]; void upd1(ll v, ll l, ll r, ll i, ll x){ if (i == l && i+1==r){ d1[v] = x; return; } else if (i < l || r <= i){ return; } upd1(v*2, l, (l+r)/2, i, x); upd1(v*2+1, (l+r)/2, r, i ,x); d1[v] = max(d1[2*v],d1[v*2+1]); } ll get1(ll v, ll l, ll r, ll sl, ll sr){ if (sl <= l && r <= sr){ return d1[v]; } else if (sr <= l || r <= sl){ return 0; } return max(get1(v*2, l,(l+r)/2, sl, sr),get1(v*2+1, (l+r)/2, r, sl, sr)); } void upd2(ll v, ll l, ll r, ll i, ll x){ if (i == l && i+1==r){ d2[v] = x; return; } else if (i < l || r <= i){ return; } upd2(v*2, l, (l+r)/2, i, x); upd2(v*2+1, (l+r)/2, r, i ,x); d2[v] = max(d2[2*v],d2[v*2+1]); } ll get2(ll v, ll l, ll r, ll sl, ll sr){ if (sl <= l && r <= sr){ return d2[v]; } else if (sr <= l || r <= sl){ return 0; } return max(get2(v*2, l,(l+r)/2, sl, sr),get2(v*2+1, (l+r)/2, r, sl, sr)); } vector<vector<ll>> changes; ll dp[200005]; ll dp1[200005]; void solve1() { ll n, x; cin >> n >> x; vector<ll> t(n); map<ll,ll> u; u[x]++; for (int i =0; i <n ;i++){ cin>>t[i]; u[t[i]]++; } int cnt= 1; for (auto &e : u){ e.second = cnt++; } x = u[x]; for (int i =0; i < n; i++){ t[i] = u[t[i]]; } ll mx = 0; for (int i = n-1; i >=0; i--){ dp[i] = get1(1, 0, cnt+1, t[i]+1, cnt+1)+1; mx =max(mx, dp[i]); changes.push_back({t[i], get1(1, 0, cnt+1, t[i], t[i]+1)}); if (changes.back()[1] < dp[i]) { upd1(1, 0, cnt+1, t[i], dp[i]); } } for (int i =0; i < n; i++){ upd1(1, 0, cnt+1, changes.back()[0],changes.back()[1]); dp1[i] = get2(1, 0, cnt+1, 0, t[i])+1; if (get2(1, 0, cnt+1, t[i] ,t[i]+1)< dp1[i]){ upd2(1, 0, cnt+1, t[i], dp1[i]); } mx= max(mx, dp1[i]); mx = max(mx, dp1[i] + get1(1, 0, cnt+1, max(0ll, t[i]-x+1), cnt+1)); changes.pop_back(); } cout<<mx; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef local freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ll t1 = 1; for (int _ = 0; _ < t1; ++_) solve1(); #ifdef local printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC); #endif }
#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...