Submission #1010912

#TimeUsernameProblemLanguageResultExecution timeMemory
1010912ByeWorldMoney (IZhO17_money)C++14
100 / 100
1010 ms69972 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") #define ll long long #define int long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<pii, int> ipii; const int MAXN = 1e6+20; const int MAXA = 9e3+20; const ll INF = 1e18+10; const int LOG = 19; const int MOD = 1e9+7; const int SQRT = 450; const vector<int> NOL = {}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const vector<int> dx = {1, -1, 0, 0}; const vector<int> dy = {0, 0, 1, -1}; int n; int a[MAXN], dp[MAXN]; set <int> s; signed main(){ cin >> n; int cnt = 0; for(int i=1; i<=n; i++) { int x; cin >> x; if(x != a[cnt]) a[++cnt] = x; } n = cnt; int las = 1; for(int i=1; i<=n; i++){ if(a[i-1] > a[i]){ for(int j=las; j<=i-1; j++) s.insert(a[j]); las = i; } // cout << las << ' ' << i << " las\n"; int less = -INF; auto it = s.lower_bound(a[i]); if(it != s.begin()) less = *(--it); // cout << less << " les\n"; int l=las, r=i, mid=0, cnt=i; while(l <= r){ mid = md; auto nw = s.upper_bound(a[mid]); if(nw == s.begin()){ if(less == -INF){ cnt = mid; r = mid-1; } else l = mid+1; } else { if(less == *(--nw)){ cnt = mid; r = mid-1; } else l = mid+1; } } // cout << cnt << "cnt\n"; dp[i] = dp[cnt-1]+1; } cout << dp[n] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...